FastPrepFastPrep
Problem Brief

Calculate Minimum Satellites Required

OA
See Google online assessment and 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.

    • 1Example 1

    Input
    targetRegions = [[1, 5], [6, 10], [11, 15]], satellites = [[1, 6], [5, 9], [10, 15]]
    Output
    3
    Explanation

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

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

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

    2Example 2

    Input
    targetRegions = [[1, 4], [5, 8], [9, 12]], satellites = [[1, 8], [4, 10], [9, 13]]
    Output
    2
    Explanation

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

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

    3Example 3

    Input
    targetRegions = [[1, 5], [6, 10], [11, 15]], satellites = [[1, 4], [6, 9]]
    Output
    -1
    Explanation

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

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

    public int calculateMinimumSatellitesRequired(int[][] targetRegions, int[][] satellites) {
  // write your code here
}
    Input

    targetRegions

    [[1, 5], [6, 10], [11, 15]]

    satellites

    [[1, 6], [5, 9], [10, 15]]

    Output

    3

    Sign in to submit your solution.