Count Essential Ranges
MediumIntervals
Problem
A sprinkler system has several zones; zone i waters the stretch ranges[i] = [left, right] of a lawn. A zone is redundant if another zone's stretch contains it entirely, that is, some other zone [c, d] has c ≤ left and right ≤ d.
All ranges are distinct. Return the number of zones that are not redundant.
Example 1
- Input:
- ranges = [[1, 4], [3, 6], [2, 8]]
- Output:
- 2
[3, 6] lies inside [2, 8]. The other two are essential.
Example 2
- Input:
- ranges = [[1, 2], [1, 4], [3, 4]]
- Output:
- 1
Both [1, 2] and [3, 4] lie inside [1, 4].
Constraints
- 1 ≤ ranges.length ≤ 10^5
- 0 ≤ left < right ≤ 10^9
- All ranges are distinct.
Hint
Show the first hint
If ranges are processed from left to right, what single number tells you whether the current one is contained in something seen before?
Walkthrough
How to approach it
01Clarify before coding
- Can a range be contained in a range with the same left end? Yes, [1, 2] is inside [1, 4].
- Are duplicates possible? No, all ranges are distinct, so containment is never mutual.
- Do we return the count of essential or redundant ranges? Essential.
02Brute force
For each range, scan all other ranges looking for one that contains it.
Cost: O(n²) time: 10^10 checks for n = 10^5.
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.