Calculate Minimum Satellites Required
Updated
Problem statement
You are given target regions and satellite ranges. Every interval [start, end] represents all integer coordinates from start through end, inclusive.
Choose the minimum number of satellites such that every integer coordinate contained in any target region is contained in at least one selected satellite range. A target region may be covered by the union of multiple selected satellites, and coordinates outside all target regions do not need coverage.
Return the minimum number of selected satellites, or -1 if complete coverage is impossible.
Function
calculateMinimumSatellitesRequired(targetRegions: int[][], satellites: int[][]) → intExamples
Example 1
targetRegions = [[1, 5], [6, 10], [11, 15]]satellites = [[1, 6], [5, 9], [10, 15]]return = 3All three satellites are required. [1,6] covers coordinates 1 through 6, [5,9] extends coverage through 9, and [10,15] covers coordinates 10 through 15.
Example 2
targetRegions = [[1, 4], [5, 8], [9, 12]]satellites = [[1, 8], [4, 10], [9, 13]]return = 2Select [1,8] and [9,13]. Their union covers every required integer coordinate from 1 through 12.
Example 3
targetRegions = [[1, 5], [6, 10], [11, 15]]satellites = [[1, 4], [6, 9]]return = -1Required coordinates 5, 10, and 11 through 15 are uncovered, so complete coverage is impossible.
Constraints
- All interval endpoints are integers.
- For every interval,
start <= end. targetRegionsis non-empty;satellitesmay be empty.
More Google interview questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Minimum RetailersAmazon · OA
- Smallest Set Covering IntervalsSnowflake · OASnowflake interview questions
- Maximum Compatible Time WindowsIBM · OAIBM interview questions
- Task SchedulingJP Morgan Chase · OAJP Morgan Chase interview questions
- Minimum Markers to Clear Line SegmentsHSBC · OAHSBC interview questions
- Minimum Machines for TasksExpedia · OAExpedia interview questions
- Meeting RoomWeWork · OAWeWork interview questions
- Meetup Schedule 📆WeRide · OAWeRide interview questions
- Most Disjoint Intervals From Starts and DurationsDocuSign · OADocuSign interview questions
- University Career FairRoblox · OARoblox interview questions
Google interview experiences
- Google L4 SWE Phone Screen: 1 Experience
- Google ML Engineering Manager Onsite: 1 Experience
- Google Experienced SWE First Round and Onsite: 1 Experience
- Google AI Coding Interview and AI OA: 2 Experiences
- Google SWE Intern Interview Results Timeline: 13 Experiences
- Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience