Problem statement

Given an array of intervals, return the minimum number of intervals to remove so the rest are non-overlapping (intervals touching only at a point do not overlap).

Example 1

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

Example 2

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

Constraints

• 1 <= intervals.length <= 20
• -50 <= start < end <= 50

Hints for Non-overlapping Intervals

1. Hint 1

   Equivalent to keeping the MAXIMUM number of non-overlapping intervals.

2. Hint 2

   Greedy: sort by end time and always keep the interval that ends earliest.

How to solve Non-overlapping Intervals

Flip the question: minimising removals is the same as keeping the most non-overlapping intervals. That is the classic activity-selection problem, and the winning greedy is to sort by end time and always keep the interval that finishes earliest — finishing early leaves the most room for everything after it.

Approach

1. Sort the intervals by their end value.
2. Track lastEnd, initially minus infinity, and a counter of kept intervals.
3. For each interval, if its start is >= lastEnd, it does not overlap what you have kept — keep it and set lastEnd to its end.
4. Otherwise skip it; it would have to be removed.
5. Return n - kept.

Why it works

Exchange argument: take any optimal selection and compare it with the greedy one at the first place they differ. The greedy interval ends no later than the optimal one — it was chosen precisely for finishing earliest among the compatible options — so substituting it keeps the selection valid and the same size. Repeating the swap transforms the optimum into the greedy solution, proving greedy is optimal. Sorting by start instead would fail: one long early interval could crowd out several short ones.

Complexity

• Time — O(n log n)
• Space — O(1)

Pitfalls

• Sort by end, not start — this is the whole trick, and sorting by start gives wrong answers on nested intervals.
• Intervals that merely touch do not overlap, so the keep test is start >= lastEnd.
• The answer is the number removed; do not return the count kept.
• Identical duplicate intervals all overlap each other, so all but one must go.

Reference solution

Python

from typing import List

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    s = sorted(intervals, key=lambda iv: iv[1])
    kept = 0
    end = float("-inf")
    for st, en in s:
        if st >= end:
            kept += 1
            end = en
    return len(intervals) - kept

Java

public static int eraseOverlapIntervals(int[][] intervals) {
    int[][] s = intervals.clone();
    Arrays.sort(s, (a, b) -> a[1] - b[1]);
    int kept = 0;
    int lastEnd = -1000000000;
    for (int[] iv : s) {
        if (iv[0] >= lastEnd) {
            kept++;
            lastEnd = iv[1];
        }
    }
    return s.length - kept;
}

C++

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    vector<vector<int>> s = intervals;
    sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    int kept = 0;
    int lastEnd = -1000000000;
    for (const auto& iv : s) {
        if (iv[0] >= lastEnd) {
            kept++;
            lastEnd = iv[1];
        }
    }
    return (int) s.size() - kept;
}

JavaScript

var eraseOverlapIntervals = function(intervals) {
    const s = intervals.slice().sort(function(a, b) { return a[1] - b[1]; });
    let kept = 0, end = -Infinity;
    for (const iv of s) {
        if (iv[0] >= end) {
            kept++;
            end = iv[1];
        }
    }
    return intervals.length - kept;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium