Non-overlapping Intervals

Problem

Given a set of intervals, return the minimum number you must remove so the remaining intervals don't overlap.

Constraints

• 1 ≤ intervals.length ≤ 10⁵

Approach — Greedy

This is a Greedy problem. The idea: make the locally best choice at each step, which provably builds up to the global optimum here. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log n) time.

Solution code

Python

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

Java

import java.util.Arrays;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.