Satellite Interval Coverage
MediumGreedy · Google
You are given targets and satellites, each a list of inclusive integer ranges [start, end]. A satellite covers every integer point from its start to its end.
Every integer point that lies in at least one target region must be covered by at least one chosen satellite. Target regions may overlap or touch each other, and points between target regions do not need coverage. A single satellite can help cover several target regions, and it counts once no matter how many it helps.
Return the minimum number of satellites to choose, 0 if targets is empty, or -1 if some target point cannot be covered by any satellite.
Example 1
- Input:
- targets = [[2, 9], [14, 18]], satellites = [[0, 5], [3, 10], [6, 15], [12, 20], [16, 30]]
- Output:
- 3
- Explanation
- The target points are 2..9 and 14..18. Choose
[0, 5]for 2..5, then[6, 15], which covers 6..9 and also 14..15 in the second region, then[12, 20](or[16, 30]) for 16..18. That is 3 satellites, and 2 cannot reach from 2 to 18.
Example 2
- Input:
- targets = [[0, 5]], satellites = [[0, 2], [3, 5]]
- Output:
- 2
- Explanation
- Coverage is about integer points, so
[0, 2]and[3, 5]together cover every point 0..5 even though they do not overlap.
Example 3
- Input:
- targets = [[0, 10]], satellites = [[0, 4], [6, 10]]
- Output:
- -1
- Explanation
- Point 5 is not covered by any satellite, so the answer is
-1.
Constraints
0 <= targets.length, satellites.length <= 10^50 <= start <= end <= 10^9for every range