Remove Covered Intervals: Sort and Count

LeetCode 1288, Remove Covered Intervals, gives you a list of intervals and asks you to remove every interval that is completely covered by another one. An interval [a, b] is covered by [c, d] when c <= a and b <= d. In other words, the first interval fits entirely inside the second. After removing all covered intervals, you return the count of what remains.

This problem sits in the same family as Merge Intervals and Non-overlapping Intervals. If you have seen those, the shape of the solution will feel familiar: sort first, then make a single greedy pass. The twist here is that you are not merging or removing overlaps. You are looking for containment.

The problem

You are given an array of intervals intervals where intervals[i] = [li, ri]. Remove all intervals that are covered by another interval in the list and return the number of remaining intervals.

Here is an example with three intervals:

The interval [3,6] sits entirely inside [2,8], so it gets removed. The intervals [1,4] and [2,8] do not cover each other (neither contains the other fully), so both survive. The answer is 2.

Why sorting makes this easy

Without sorting, you would need to compare every pair of intervals to check for containment. That is O(n^2). But if you sort the intervals by start time ascending, and break ties by end time descending, you create a useful invariant: for any interval you are currently looking at, every interval that could possibly cover it has already been processed.

Why break ties by end descending? Consider two intervals that start at the same point, like [1,4] and [1,7]. The longer one [1,7] covers the shorter one [1,4]. By placing the longer interval first in the sorted order, you process it before the shorter one. When you reach [1,4], you already know that maxEnd is at least 7, so [1,4] correctly gets flagged as covered.

The algorithm

1. Sort the intervals by start ascending, breaking ties by end descending.
2. Initialize a counter and a max_end tracker set to 0.
3. Scan through each interval. If the current interval's end is greater than max_end, it is not covered. Increment the counter and update max_end. Otherwise, skip it.

That is the whole thing. One sort, one pass, one variable to track.

def remove_covered_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: (x[0], -x[1]))
    count = 0
    max_end = 0

    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end

    return count

The negative sign on x[1] in the sort key is the critical detail. It flips the tie-breaking order so that among intervals with the same start, the longest one comes first.

Visual walkthrough

Let's trace through [[1,4],[3,6],[2,8]]. After sorting by start ascending and end descending, the order becomes [1,4], [2,8], [3,6].

The key moment is step 3. When we process [3,6], its end value 6 is not greater than max_end (which is 8 from the previous step). That means some earlier interval already extends past [3,6], so it is fully covered. We skip it.

Why the greedy check works

After sorting, every interval you encounter has a start value greater than or equal to all previously seen starts. So you only need to check one thing: does this interval's end extend past the farthest end you have seen so far?

If end > max_end, this interval reaches further right than anything before it. No previous interval can contain it, because they all end at or before max_end. So it survives.

If end <= max_end, some previous interval has a start that is at most the current start (guaranteed by sorting) and an end that is at least the current end. That previous interval covers the current one completely.

Complexity analysis

Time: O(n log n). Sorting dominates. The scan is O(n).

Space: O(1) beyond the sort itself. Python's sort() uses O(n) auxiliary space internally (Timsort), but the algorithm needs no extra data structures. If you count the sort's internal memory, it is O(n).

The building blocks

Remove Covered Intervals is built from two patterns that appear throughout interval problems on LeetCode.

Sort with custom tie-breaking

The standard interval sort is "sort by start." This problem adds a twist: break ties by end descending. That single detail is what makes the greedy scan correct. You will see similar custom sort orders in problems where the default ordering is almost right but needs a tweak for edge cases.

This pattern shows up in:

• Merge Intervals (sort by start, then sweep and merge neighbors)
• Non-overlapping Intervals (sort by end, then greedily keep compatible intervals)
• Meeting Rooms II (sort by start, then track overlaps with a heap)

Whenever a greedy approach almost works but breaks on ties, check whether a custom tie-breaking rule in the sort fixes it.

Greedy scan with running maximum

You maintain a single variable (max_end) as you walk through the sorted array. Each element either updates the running state or gets eliminated. No backtracking, no recursion, no auxiliary data structures. This is greedy at its simplest.

The same "track a running maximum" idea appears in:

• Jump Game (track the farthest index you can reach)
• Best Time to Buy and Sell Stock (track the minimum price seen so far)
• Container With Most Water (track the best area while shrinking the window)

If your problem reduces to "scan a sorted array and make a keep/skip decision based on one running value," you are likely looking at this pattern.

Edge cases

Single interval. If there is only one interval, it cannot be covered by anything. The answer is 1. The code handles this naturally since the loop runs once and increments the counter.

No intervals are covered. If the intervals are all disjoint (like [1,2], [3,4], [5,6]), every interval's end exceeds max_end. The count equals the number of intervals.

All intervals share the same start. For [1,2], [1,5], [1,8], after sorting by end descending, the order is [1,8], [1,5], [1,2]. Only [1,8] survives because 5 and 2 are both less than or equal to 8.

Nested intervals. For [1,10], [2,5], [3,4], the outer interval covers everything inside it. After sorting: [1,10], [2,5], [3,4]. Only [1,10] has an end exceeding max_end.

Identical intervals. If the input contains duplicates like [1,4], [1,4], the sort places them adjacent. The first one sets max_end = 4. The second has end = 4, which is not greater than max_end, so it is covered. The count is 1. This is correct per the problem definition.

From understanding to recall

You have seen the pattern: sort by start ascending with end descending as the tie-breaker, then scan while tracking max_end. The logic is compact. But will you remember the sort key (x[0], -x[1]) two weeks from now? Will you remember why the negative sign matters?

Interval containment is a specific shape within the broader interval family. It is not merging (where you combine overlapping ranges) and it is not scheduling (where you pick non-conflicting intervals). It is a third flavor, and it has its own sorting trick. Drilling this problem in isolation helps you distinguish it from the others when you see a new interval problem.

Spaced repetition works well here because the solution is short but the reasoning behind the sort order is subtle. The first time you revisit it, you might fumble the tie-breaking direction. By the third review, the (start, -end) key will feel automatic.

Related posts

• Merge Intervals - The foundational interval problem, sort by start and sweep to merge overlapping ranges
• Insert Interval - Insert into a sorted interval list and merge on the fly
• Non-overlapping Intervals - Sort by end time and greedily keep compatible intervals

---