Google OA Question

Round 1

Questions: 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.

Test Cases: 1.

• targetRegions = [[1, 5], [6, 10], [11, 15]]
• satellites = [[1, 6], [5, 9], [10, 15]]
• Expected 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].

2. • targetRegions = [[1, 4], [5, 8], [9, 12]]
   • satellites = [[1, 8], [4, 10], [9, 13]]
   • Expected Output: 2
   • Explanation:
     • Satellite [1, 8] covers [1, 4] and [5, 8].
     • Satellite [9, 13] covers [9, 12].
3. • targetRegions = [[1, 5], [6, 10], [11, 15]]
   • satellites = [[1, 4], [6, 9]]
   • Expected Output: -1
   • Explanation:
     • Satellite [1, 4] cannot fully cover [1, 5].
     • The target region [11, 15] is not covered.