DSA problem
Remove Covered Intervals
Given an array intervals where intervals[i] = [l_i, r_i] represents the inclusive interval [l_i, r_i], remove all intervals that are covered by another interval in the list. The interval [a, b] is covered by [c, d] if and only if c <= a and b <= d. Return the number of remaining intervals after removing all covered intervals.
A first instinct is to check every pair of intervals for coverage, costing O(n^2). Sorting transforms the problem into an O(n log n) sweep that visits each interval just once. The right sort order is the key insight: sort by start ascending, and when starts tie, by end descending.
Why that tie-breaker? After sorting by start ascending, any interval that comes later has a start at least as large as the previous one, so its left endpoint is never to the left of an earlier interval. Equal starts complicate the picture because if two intervals share the same start, the shorter one is covered by the longer one. Putting the longer (larger end) first ensures the shorter ones come after and will be detected as covered.
The optimal algorithm sweeps once tracking the maximum end seen so far. For each new interval, if its end is strictly greater than the running max end, the interval is not covered (it extends past everything before it), so increment the count and update the max end. Otherwise the interval is covered and is silently skipped. Return the count of kept intervals.
Examples
intervals = [[1,4],[3,6],[2,8]]2intervals = [[1,4],[2,3]]1intervals = [[0,10],[5,12]]2Constraints
- 1 <= intervals.length <= 1000
- intervals[i].length == 2
- 0 <= l_i <= r_i <= 10^5
- All the given intervals are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.