Non-overlapping Intervals

Medium Problem 143 of 151 Java and Python

Problem

Given an array of intervals, return the minimum number of intervals you need to remove so that the remaining intervals do not overlap.

Intervals that only touch (like [1, 2] and [2, 3]) do not overlap.

Example 1

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Why: Remove [1, 3].

Example 2

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

Example 3

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Constraints

1 ≤ intervals.length ≤ 10⁵
-5 × 10⁴ ≤ startᵢ < endᵢ ≤ 5 × 10⁴

Explanation

Removing the fewest is the same as keeping the most non-overlapping intervals (activity selection). The greedy rule: among intervals that fit, always keep the one that ends earliest, because it leaves the most room for the rest.

Sort by end, keep an interval whenever it starts at or after the last kept end, and count the others as removed.

Approach 1 · Better

DP over intervals sorted by start

Time O(n²)
Space O(n)

Like Longest Increasing Subsequence: keep[i] is the most intervals you can keep ending with interval i.

Sort by start.
keep[i] = 1 + max(keep[j]) over j < i with end[j] <= start[i].
Answer = n - max(keep).

Java

import java.util.*;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int n = intervals.length;
        int[] keep = new int[n];
        int best = 0;
        for (int i = 0; i < n; i++) {
            keep[i] = 1;
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    keep[i] = Math.max(keep[i], keep[j] + 1);
                }
            }
            best = Math.max(best, keep[i]);
        }
        return n - best;
    }
}

Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals)
        n = len(intervals)
        keep = [1] * n
        for i in range(n):
            for j in range(i):
                if intervals[j][1] <= intervals[i][0]:
                    keep[i] = max(keep[i], keep[j] + 1)
        return n - max(keep)

Approach 2 · Optimal

Greedy by earliest end

Time O(n log n)
Space O(1) extra

Sort by end. Keep each interval that starts at or after the last kept end; every other interval is removed.

Sort intervals by end.
lastEnd = -infinity, removed = 0.
For each interval: if start >= lastEnd, keep it (lastEnd = end); otherwise removed++.

Java

import java.util.*;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int removed = 0;
        int lastEnd = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] >= lastEnd) {
                lastEnd = interval[1];
            } else {
                removed++;
            }
        }
        return removed;
    }
}

Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        removed, last_end = 0, float("-inf")
        for start, end in sorted(intervals, key=lambda x: x[1]):
            if start >= last_end:
                last_end = end
            else:
                removed += 1
        return removed

Complexity compared

Approach	Time	Space
Better DP over intervals sorted by start	O(n²)	O(n)
Optimal Greedy by earliest end	O(n log n)	O(1) extra

Key takeaways

Sort by end when choosing intervals to keep; sort by start when merging.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem