FastPrep
Problem · Intervals

Calculate Minimum Satellites Required

● HardGoogleOA
See Google hiring insights

ISRO is tasked with launching a set of satellites to monitor specific regions on Earth. Each satellite has a limited range within which it can gather data. The goal is to deploy the minimum number of satellites necessary to cover a set of target regions on Earth completely.

You are given:

  • An array of target regions, each represented as an interval [start, end], which shows the latitude range of Earth that requires monitoring.
  • A set of satellites, each having a monitoring range [coverageStart, coverageEnd].

    • Write an algorithm to calculate the minimum number of satellites required to cover all given target regions completely. If coverage is not possible, return -1.

    Additional Details:

  • Each satellite can cover any region within its range.
  • Overlapping satellite ranges can be used to extend coverage.
  • No partial coverage is allowed—a region must be fully covered by one or more satellites.

    • Examples
    01 · Example 1
    targetRegions = [[1, 5], [6, 10], [11, 15]]
satellites = [[1, 6], [5, 9], [10, 15]]
return = 3

    The satellite [1, 6] fully covers [1, 5].

    The satellite [5, 9] covers [6, 10] (with overlap).

    The satellite [10, 15] covers [11, 15].

    02 · Example 2
    targetRegions = [[1, 4], [5, 8], [9, 12]]
satellites = [[1, 8], [4, 10], [9, 13]]
return = 2

    Satellite [1, 8] covers [1, 4] and [5, 8].

    Satellite [9, 13] covers [9, 12].

    03 · Example 3
    targetRegions = [[1, 5], [6, 10], [11, 15]]
satellites = [[1, 4], [6, 9]]
return = -1

    Satellite [1, 4] cannot fully cover [1, 5].

    The target region [11, 15] is not covered.

    More Google problems
    drafts saved locally
    public int calculateMinimumSatellitesRequired(int[][] targetRegions, int[][] satellites) {
  // write your code here
}
    targetRegions[[1, 5], [6, 10], [11, 15]]
    satellites[[1, 6], [5, 9], [10, 15]]
    expected3
    sign in to submit