Problem 15.5 · IntervalsMedium

Non-overlapping Intervals

What it teaches: Activity selection: sort by end, keep every interval compatible with the last kept, and remove the rest.

Practise it on judges as “Non-overlapping Intervals”.

The problem

Return the minimum number of intervals to remove so the rest don't overlap. Intervals that only touch (like [1,2] and [2,3]) don't overlap.

Example 1

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1

Example 2

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

Constraints

1 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Keep the most intervals without overlap
→ Greedy by earliest end

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	intervals = [[1,2],[2,3],[3,4],[1,3]]	1
2	intervals = [[1,2],[1,2],[1,2]]	2
3	intervals = [[1,2],[2,3]]	0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: greedy by end time · O(n log n)

Optimal: greedy by end time

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

Sort by end. keep = 0, lastEnd = −∞. For each interval with start ≥ lastEnd, keep it and set lastEnd = end. Answer = n − keep.

Approach 1

import java.util.Arrays;

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

Verdict: Proven optimal by the exchange argument.

Before you submit

Edge cases and common mistakes

Test these inputs

Identical intervals
Nested intervals
Already non-overlapping → 0

Mistakes people make

Sorting by start without care (a long early interval blocks many).
Using > instead of >= (touching intervals are allowed).

Interview

Follow-up questions

Why does sorting by start fail with a naive rule?

Command Palette

The problem

Approaches

Optimal: greedy by end time

Edge cases and common mistakes

Follow-up questions

Related problems