MediumArrayGreedySortingIntervals

Non-overlapping Intervals

1 approach, code in every language

Given a set of intervals, figure out the smallest number of them you would need to delete so that the ones left behind never overlap. Intervals that only share an endpoint are considered compatible and do not need to be removed.

Return that minimum deletion count. This is equivalent to keeping the largest possible set of mutually compatible intervals and removing everything else.

Example 1

Input: intervals = [[1,2],[2,4],[1,4]]

Output: 1

Dropping [1,4] leaves [1,2] and [2,4], which only touch at 2 and so do not overlap.

Example 2

Input: intervals = [[1,3],[1,3],[1,3]]

Output: 2

All three cover the same span, so two of the duplicates must go.

Constraints

1 ≤ intervals.length ≤ 10^5
intervals[i].length == 2
-5 * 10^4 ≤ start < end ≤ 5 * 10^4

Greedy by earliest finish

Sort by end value and always keep the interval that finishes soonest, counting every interval that clashes with the last kept one as a removal.

Loading animation…

Intuition

This mirrors the classic activity-selection idea. If we always hold onto the interval that ends the earliest, we leave the maximum amount of room for future intervals to fit without conflict. Sorting by end value lets us scan left to right and greedily accept an interval whenever its start is at or after the end of the last one we kept. Anything that starts too early to fit is counted as a deletion, and this locally optimal choice provably yields the globally minimal number of removals.

Algorithm walkthrough

1Sort the intervals in ascending order of their end value.
2Track the end of the most recently kept interval, starting at negative infinity.
3For each interval, if its start is at least the tracked end, keep it and update the tracked end.
4Otherwise it overlaps the kept interval, so increment the removal counter and leave the tracked end alone.
5Return the removal counter once every interval has been processed.

Implementation

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        count = 0
        prev_end = float('-inf')
        for start, end in intervals:
            if start >= prev_end:
                prev_end = end
            else:
                count += 1
        return count

Time

O(n log n)

Space

O(1)

Sorting by end value costs O(n log n); the greedy scan is linear and uses only a couple of scalar variables beyond the sort.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Drop the Clashing Kiln Runs is our own problem on the technique behind Non-overlapping Intervals: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free