Cover the Whole Shift
MediumIntervals
Problem
A security shift runs from time 0 to time shiftLength. Each guard in offers is available for the closed range [from, to]. Two guards hand over seamlessly when one's to equals or exceeds the next one's from.
Return the minimum number of guards needed so that every moment of [0, shiftLength] is covered, or -1 if it is impossible.
Example 1
- Input:
- offers = [[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], shiftLength = 10
- Output:
- 3
[0, 2] → [1, 9] → [8, 10] covers everything.
Example 2
- Input:
- offers = [[0, 1], [1, 2]], shiftLength = 5
- Output:
- -1
Nobody is available after time 2.
Constraints
- 1 ≤ offers.length ≤ 10^5
- 0 ≤ from ≤ to ≤ 10^9
- 1 ≤ shiftLength ≤ 10^9
Hint
Show the first hint
Some guard must cover time 0. Among those, which one is best to pick?
Walkthrough
How to approach it
01Clarify before coding
- Does touching count as a handover? Yes, [0, 2] then [2, 5] covers [0, 5].
- May a guard extend beyond the shift? Yes, that is fine.
- Should impossible cases return -1? Yes.
02Brute force
Try every subset of offers in increasing size and check whether it covers [0, shiftLength].
Cost: Exponential.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.