FastPrep

Description

Solutions

Calculate Minimum Satellites Required

📚RELATED PROBLEMS

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.

Example 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].

Example 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].

Example 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.

Constraints:

:)