LeetCode 435: Non-overlapping Intervals

Problem Restatement

We are given an array of intervals.

Each interval has a start and an end:

[start, end]

We need to remove the minimum number of intervals so that the remaining intervals do not overlap.

Two intervals that only touch at an endpoint do not overlap.

For example:

[1, 2]
[2, 3]

These can both remain, because the first interval ends exactly when the second interval starts.

The official problem asks us to return the minimum number of intervals that must be removed so the rest are non-overlapping.

Input and Output

Example function shape:

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    ...

Examples

Example 1:

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]

We can remove:

[1, 3]

The remaining intervals are:

[[1, 2], [2, 3], [3, 4]]

They do not overlap.

Answer:

1

Example 2:

intervals = [[1, 2], [1, 2], [1, 2]]

All intervals are identical. We can keep only one.

Answer:

2

Example 3:

intervals = [[1, 2], [2, 3]]

They only touch at endpoint 2, so they do not overlap.

Answer:

0

First Thought: Try Every Subset

One way to think about the problem is:

Find the largest subset of intervals that do not overlap.

Then:

answer = total_intervals - largest_non_overlapping_subset_size

But trying every subset is too slow.

For n intervals, there are:

2 ** n

possible subsets.

We need a greedy method.

Key Insight

To remove the fewest intervals, we should keep as many intervals as possible.

This is the classic interval scheduling problem.

The best greedy rule is:

Sort intervals by their end time, then keep every interval that starts after or at the end of the last kept interval.

Why sort by end time?

Because an interval that ends earlier leaves more room for future intervals.

For example:

[1, 10]
[2, 3]
[3, 4]
[4, 5]

If we keep [1, 10], we block many smaller intervals.

If we keep [2, 3], we still have room for [3, 4] and [4, 5].

So the greedy choice is to keep the interval with the earliest end.

Algorithm

Sort intervals by end time:

intervals.sort(key=lambda x: x[1])

Initialize:

removed = 0
prev_end = intervals[0][1]

Then scan from the second interval.

For each interval [start, end]:

If:

start < prev_end

then this interval overlaps with the last kept interval, so we remove it:

removed += 1

Otherwise, we keep it and update:

prev_end = end

Return:

removed

Because the intervals are sorted by end time, when an overlap occurs, removing the current interval is safe. The previously kept interval ends no later than the current interval, so keeping the previous interval leaves at least as much room for future intervals.

Correctness

After sorting by end time, the algorithm considers intervals from earliest finishing to latest finishing.

Whenever the current interval starts at or after prev_end, it does not overlap with the last kept interval. The algorithm keeps it, and this increases the number of kept intervals by one.

Whenever the current interval starts before prev_end, it overlaps with the last kept interval. Since the last kept interval has an end time less than or equal to the current interval’s end time, keeping the last kept interval is at least as good for all future intervals. It leaves the same or more remaining timeline available.

Therefore, in every overlap case, removing the current interval does not reduce the maximum possible number of intervals we can keep.

The algorithm greedily constructs a maximum-size set of non-overlapping intervals. Since the minimum number removed equals:

len(intervals) - maximum_number_kept

the returned removal count is minimal.

Complexity

The scan after sorting is O(n).

Implementation

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: x[1])

        removed = 0
        prev_end = intervals[0][1]

        for start, end in intervals[1:]:
            if start < prev_end:
                removed += 1
            else:
                prev_end = end

        return removed

Code Explanation

We sort by interval end:

intervals.sort(key=lambda x: x[1])

This lets us prefer intervals that finish earliest.

We keep the first interval after sorting:

prev_end = intervals[0][1]

Then we scan the rest.

If the current interval starts before the previous kept interval ends:

if start < prev_end:

the two intervals overlap, so we remove the current interval:

removed += 1

Notice that we do not update prev_end in this case. The previous kept interval ends earlier or at the same time because of the sorting order.

If there is no overlap:

else:
    prev_end = end

we keep the current interval and update the end boundary.

Testing

def run_tests():
    s = Solution()

    assert s.eraseOverlapIntervals(
        [[1, 2], [2, 3], [3, 4], [1, 3]]
    ) == 1

    assert s.eraseOverlapIntervals(
        [[1, 2], [1, 2], [1, 2]]
    ) == 2

    assert s.eraseOverlapIntervals(
        [[1, 2], [2, 3]]
    ) == 0

    assert s.eraseOverlapIntervals(
        [[1, 100], [11, 22], [1, 11], [2, 12]]
    ) == 2

    assert s.eraseOverlapIntervals(
        [[-52, 31], [-73, -26], [82, 97], [-65, -11], [-62, -49], [95, 99], [58, 95], [-31, 49], [66, 98], [-63, 2], [30, 47], [-40, -26]]
    ) == 7

    print("all tests passed")

run_tests()

Test meaning: