132.Non Overlapping Intervals

MediumBlind 75Intervals · 3/6

Problem

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals to remove so that the remaining intervals do not overlap.

Here intervals that only touch at a point do not overlap: [1,2] and [2,3] can both stay.

Examples

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: Remove [1,3]; [1,2],[2,3],[3,4] are pairwise non-overlapping.

Input:  intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: Only one copy of [1,2] can stay.

Input:  intervals = [[1,2],[2,3]]
Output: 0
Explanation: Touching endpoints are allowed.

Constraints

1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= start_i < end_i <= 5 * 10^4

💡 Key Insight

Minimizing removals is the same as maximizing the number of intervals kept (classic activity selection). Greedily keep the interval that ends earliest: it leaves the most room for everything after it, and an exchange argument shows any optimal schedule can be rewritten to start with that interval. Sort by end, keep each interval whose start is >= the last kept end, and count the rest as removals.

Brute Force (Recursion: Keep or Remove)

TimeO(2^n)SpaceO(n)

Intuition

Sort by start, then for each interval try both choices: keep it (only allowed if it starts at or after the last kept end) or remove it (cost 1). Return the cheaper branch. This explores every subset.

Algorithm

Sort by start.
solve(i, prevEnd): if i == n return 0.
remove = 1 + solve(i + 1, prevEnd).
If intervals[i][0] >= prevEnd, keep = solve(i + 1, intervals[i][1]).
Return min(keep, remove); start with solve(0, -infinity).

Visualization

flowchart TD
    R["i=0 [1,2]<br/>prevEnd = -inf"] -->|"keep"| K["i=1 [1,3]<br/>prevEnd = 2"]
    R -->|"remove +1"| X["i=1 [1,3]<br/>prevEnd = -inf"]
    K -->|"1 < 2: must remove +1"| K2["i=2 [2,3]<br/>prevEnd = 2"]
    K2 -->|"keep"| K3["i=3 [3,4]<br/>prevEnd = 3"]
    K3 -->|"keep"| K4["done: 1 removal"]

(sorted input: [1,2],[1,3],[2,3],[3,4])

Code

java

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        return solve(intervals, 0, Integer.MIN_VALUE);
    }

    private int solve(int[][] intervals, int i, int prevEnd) {
        if (i == intervals.length) {
            return 0;
        }
        int best = 1 + solve(intervals, i + 1, prevEnd); // remove interval i
        if (intervals[i][0] >= prevEnd) {
            best = Math.min(best, solve(intervals, i + 1, intervals[i][1])); // keep it
        }
        return best;
    }
}

Complexity

Time: O(2^n) — two branches per interval.
Space: O(n) — recursion depth.

Dynamic Programming (Longest Chain)

TimeO(n²)SpaceO(n)

Intuition

After sorting by start, the kept intervals form a chain where each starts at or after the previous one ends. Let dp[i] be the longest such chain ending with interval i. Then dp[i] = 1 + max(dp[j]) over earlier j with end_j <= start_i. The answer is n - max(dp). This is the Longest Increasing Subsequence pattern.

Algorithm

Sort by start.
For each i: dp[i] = 1; for each j < i with intervals[j][1] <= intervals[i][0], dp[i] = max(dp[i], dp[j] + 1).
Return n - max(dp).

Visualization

Sorted: [1,2],[1,3],[2,3],[3,4]

i	interval	compatible earlier j	dp[i]
0	[1,2]	—	1
1	[1,3]	none (ends 2 > 1)	1
2	[2,3]	j=0	2
3	[3,4]	j=0, 1, 2	3

max(dp) = 3, so remove 4 - 3 = 1.

Code

java

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int[] dp = new int[n]; // dp[i] = longest non-overlapping chain ending at i
        int longest = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            longest = Math.max(longest, dp[i]);
        }
        return n - longest;
    }
}

Complexity

Time: O(n²) — the double loop (too slow for n = 10^5, but a correct stepping stone).
Space: O(n) — the dp array.

Greedy by Earliest EndOptimal

TimeO(n log n)SpaceO(log n)

Intuition

Among all intervals that could come next, the one that finishes first is never a worse choice: swapping it into any optimal solution keeps it valid and frees more space for the future. So sort by end, sweep, and keep an interval whenever it starts at or after the last kept end. Every interval that conflicts is removed.

Algorithm

Sort by end.
prevEnd = -infinity, removed = 0.
For each interval: if start >= prevEnd, keep it (prevEnd = end); else removed++.
Return removed.

Dry Run

Sorted by end: [1,2],[2,3],[1,3],[3,4]

time:    1     2     3     4
[1,2]    [-----]                 start 1 >= -inf -> keep, prevEnd = 2
[2,3]          [-----]           start 2 >= 2    -> keep, prevEnd = 3
[1,3]    [-----------]           start 1 <  3    -> remove (removed = 1)
[3,4]                [-----]     start 3 >= 3    -> keep, prevEnd = 4

flowchart LR
    A["prevEnd = -inf"] -->|"keep [1,2]"| B["prevEnd = 2"]
    B -->|"keep [2,3]"| C["prevEnd = 3"]
    C -->|"remove [1,3]"| D["removed = 1"]
    D -->|"keep [3,4]"| E["prevEnd = 4<br/>answer 1"]

Code

java

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // earliest end first
        int removed = 0;
        int prevEnd = Integer.MIN_VALUE;
        for (int[] in : intervals) {
            if (in[0] >= prevEnd) {
                prevEnd = in[1]; // compatible: keep it
            } else {
                removed++; // overlaps the last kept interval
            }
        }
        return removed;
    }
}

Complexity

Time: O(n log n) — sorting; the sweep is O(n).
Space: O(log n) — sort stack; no other storage.

Complexity Comparison

Approach	Time	Space
Recursion (Keep or Remove)	O(2^n)	O(n)
DP (Longest Chain)	O(n²)	O(n)
Greedy by Earliest End	O(n log n)	O(log n)

Common Pitfalls

Treating touching intervals as overlapping — [1,2] and [2,3] are compatible here, so the check is start >= prevEnd, not >.
Sorting by start and greedily keeping the first interval — [1,100],[2,3],[4,5] would keep [1,100] and remove two. (Sort by start works only if, on conflict, you keep the one with the smaller end.)
Initializing prevEnd = 0 — starts can be negative (down to -5 · 10^4).
Returning the number of kept intervals instead of n - kept.