Remove Covered Intervals (LeetCode 1288)

The problem

You get a list of intervals [a, b). Interval [a, b) is covered by [c, d) if c <= a and b <= d. Remove every covered interval and return how many remain.

Input:  intervals = [[1, 4], [3, 6], [2, 8]]
Output: 2

[3, 6] lies inside [2, 8], so it goes. [1, 4] and [2, 8] overlap but neither contains the other, so both stay.

How to think about it

Start with brute force. For each interval, check every other interval to see whether it covers this one. That is O(n²) comparisons. Fine for 1,000 intervals, but there is a cleaner way.

The key insight: sort so that covering intervals come first. Sort by start ascending. Then any interval that could cover the current one appears before it, since a cover must start at or before it. Among intervals with the same start, put the longer one first (end descending). That way, when two share a start, the bigger one is seen first and the smaller one is correctly flagged as covered.

After sorting, one number tells you everything. Keep prev_end, the largest end seen so far. Every earlier interval starts at or before the current one. So the current interval is covered if and only if some earlier end reaches at least as far: e <= prev_end. If e > prev_end, it sticks out past everything before it, so it survives and becomes the new furthest end.

Which pattern is this? Intervals with a greedy sweep. The tell is “intervals” plus a containment or overlap question: sort by start, then sweep with a running maximum.

Approach

1. Sort intervals by (start, -end): start ascending, end descending on ties.
2. Set count = 0 and prev_end = 0.
3. For each interval (s, e): if e > prev_end, it isn’t covered. Add one to count and set prev_end = e.
4. Otherwise it is covered by an earlier interval; skip it.
5. Return count.

Solution

def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], -x[1]))   # same start: longer interval first
    count = 0; prev_end = 0
    for s, e in intervals:
        if e > prev_end:            # sticks out past every earlier interval: survives
            count += 1; prev_end = e
    return count
# remove_covered_intervals([[1,4],[3,6],[2,8]]) -> 2

Dry run

After sorting: [[1, 4], [2, 8], [3, 6]].

The answer is 2.

Complexity

• Time: O(n log n). The sort dominates; the sweep is O(n).
• Space: O(1) extra. Two variables, besides the space the sort uses.

Edge cases and pitfalls

• Single interval returns 1.
• Equal starts are the trap. With [[1, 2], [1, 4]] sorted by start only, [1, 2] comes first and both get counted. The -x[1] tie-break puts [1, 4] first so [1, 2] is caught.
• Identical intervals cover each other; only one survives, which this code handles.
• Starting prev_end at 0 works because LeetCode guarantees non-negative coordinates. Use -inf if negatives are possible.
• Mixing up covered and overlapping: overlapping intervals both survive; only full containment removes one.

Related problems

• Merge Intervals (LeetCode 56): the same sort-then-sweep, merging instead of counting.
• Non-overlapping Intervals (LeetCode 435): greedy removal, sorted by end time.
• Minimum Number of Arrows to Burst Balloons (LeetCode 452): another interval greedy driven by a running boundary.