Two Checkpoints Each
HardIntervals
Problem
A marathon route has several zones, each [from, to] (both ends included, from < to). Race officials want water stations at integer positions so that every zone contains at least two stations.
Return the minimum number of stations needed.
Example 1
- Input:
- zones = [[1, 3], [3, 7], [8, 9]]
- Output:
- 5
Stations at 2, 3, 7, 8, 9: [1, 3] has 2 and 3, [3, 7] has 3 and 7, [8, 9] has 8 and 9.
Example 2
- Input:
- zones = [[1, 5], [2, 6], [3, 7]]
- Output:
- 2
Stations at 4 and 5 lie in all three zones.
Constraints
- 1 ≤ zones.length ≤ 3000
- 0 ≤ from < to ≤ 10^8
Hint
Show the first hint
With one station per zone, you would place it at the right end of the zone that ends first. What changes with two?
Walkthrough
How to approach it
01Clarify before coding
- Must stations be at integer positions? Yes, which is why right - 1 is a valid second choice (from < to guarantees it lies in the zone).
- Can one station count for several zones? Yes, that is the whole point.
- Are zones sorted? No.
02Brute force
Try every set of candidate positions (zone endpoints and their neighbours) in increasing size until all zones have two.
Cost: Exponential in the number of candidate positions.
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.