How should I practice Calculate Minimum Satellites Required?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google online assessment problems in FastPrep.

Is Calculate Minimum Satellites Required associated with Google?

FastPrep tags this as a Google online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Intervals

Calculate Minimum Satellites Required

Learn this problem

● Hard

GoogleOA

See Google hiring insights

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[][]) → int

Examples

Example 1

targetRegions = [[1, 5], [6, 10], [11, 15]]satellites = [[1, 6], [5, 9], [10, 15]]return = 3

All 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 = 2

Select [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 = -1

Required 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.
targetRegions is non-empty; satellites may be empty.