MediumBlind75ArrayDPGreedy

Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Examples

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

[1,3] can be removed, leaving [[1,2],[2,3],[3,4]] which is non-overlapping.

Input
intervals = [[1,2],[1,2],[1,2]]
Output
2

You need to remove two [1,2] intervals to make the rest non-overlapping.

Constraints

  • •1 <= intervals.length <= 10^4
  • •intervals[i].length == 2
  • •-5 * 10^4 <= starti < endi <= 5 * 10^4

Approaches

Try all subsets of intervals and find the largest non-overlapping set.

CodeT: O(2^n) | S: O(n)
def erase_overlap_intervals(intervals):
    def helper(i, prev_end):
        if i == len(intervals):
            return 0
        skip = helper(i + 1, prev_end)
        if intervals[i][0] >= prev_end:
            take = 1 + helper(i + 1, intervals[i][1])
        else:
            take = float('inf')
        return min(skip, take)
    intervals.sort(key=lambda x: x[0])
    return helper(0, float('-inf'))

Sort by end time, greedily keep intervals that end earliest.

CodeT: O(n log n) | S: O(1)
def erase_overlap_intervals(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])
    count = 0
    prev_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] >= prev_end:
            prev_end = intervals[i][1]
        else:
            count += 1
    return count

Same greedy approach with cleaner implementation.

Diagram

intervals = [[1,2],[2,3],[3,4],[1,3]] Sorted by end: [[1,2],[1,3],[2,3],[3,4]] [1,2]: start=1 >= end=-inf, keep, end=2 [1,3]: start=1 < end=2, remove, count=1 [2,3]: start=2 >= end=2, keep, end=3 [3,4]: start=3 >= end=3, keep, end=4 Result: 1
CodeT: O(n log n) | S: O(1)
def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    end = float('-inf')
    removed = 0
    for start, finish in intervals:
        if start >= end:
            end = finish
        else:
            removed += 1
    return removed

Complexity Comparison

Brute Force - Try All Subsets
T: O(2^n)S: O(n)

Try all subsets of intervals and find the largest non-overlapping set.

Greedy - Sort by End
T: O(n log n)S: O(1)

Sort by end time, greedily keep intervals that end earliest.

Optimized Greedy
T: O(n log n)S: O(1)

Same greedy approach with cleaner implementation.

Common Mistakes

Not sorting intervals by end time

Using a DP approach when greedy is more efficient

Not handling the case where intervals have the same end time

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems