Difficulty: MediumIntervals

Non-overlapping Intervals

Problem in Plain English

You are given a list of intervals and may delete any of them. Return the smallest number of deletions that leaves the remaining intervals pairwise non-overlapping.

Problem Statement

Given a nonempty list intervals of positive-length intervals [start, end], remove the fewest intervals so the remaining ones are pairwise non-overlapping. Return the removal count, not the retained intervals.

Intervals sharing only an endpoint are compatible: [1,2] and [2,3] may both remain. Input order is arbitrary and endpoints may be negative. The implementations below preserve the original outer order and all row values.

Constraints

$1 \leq n = \mathrm{intervals.length} \leq 10^5$ .
Every interval contains exactly two integer endpoints.
$-5 \times 10^4 \leq \mathrm{start}_i < \mathrm{end}_i \leq 5 \times 10^4$ .

Examples

Example 1

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

Remove [1,3] and the remaining [1,2], [2,3], [3,4] are pairwise non-overlapping.

Example 2

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

Keep any one copy of [1,2] and remove the other two.

Example 3

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

The intervals only touch at 2, so nothing needs removing.

Example 4

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

Remove the long interval [0,10] and keep all three short intervals. Keeping the earliest-starting interval instead would force three removals.

Example 5

Input: intervals = [[-5,-1]]
Output: 0

A single interval never conflicts with another. Negative endpoint values do not change the compatibility test.

Intuition

Minimizing removals is equivalent to maximizing how many intervals we keep. In Example 1, keeping [1,2], [2,3], and [3,4] beats keeping the longer [1,3] with [3,4]. An interval ending sooner leaves at least as much room for every future choice. That suggests sorting by end and accepting compatible intervals, while exhaustive keep-or-drop choices provide a direct baseline for small inputs. Endpoint contact is allowed here, unlike closed-interval merging.

Approaches

Exhaustive Subsets

Solution Details

Reveal Exhaustive Subsets: intuition, complexity, and code

Intuition

Examine every keep-or-drop subset, reject those containing a conflicting pair, and retain the largest feasible size. A Boolean-array counter enumerates subsets without fixed-width bit shifts or recursion. Two simple preliminary checks settle already-compatible inputs and inputs sharing a common occupied time, so those maximum-size families do not enter the exponential search.

Step-by-Step Logic

First check two direct cases: sort copied row references by start to test whether all intervals are compatible, and compare the maximum start with the minimum end to test whether every interval shares a common occupied time. Return 0 or n - 1 respectively when proved. Example 1 satisfies neither check.
Initialize one false Boolean per interval and best = 0. Enumerate each keep-or-drop vector, toggling index 0 fastest and carrying through true entries; no integer mask or recursive call stack is used. Example 1 has sixteen vectors.
For each vector count kept intervals and test every kept pair. A pair conflicts only if each start is strictly before the other end. In Example 1, subset indices {0,1,2} has size 3 and is compatible, while {0,3} conflicts.
Update best only for a feasible subset. Continue until the Boolean counter carries beyond the final position. Example 1 has largest feasible size 3, so return 4 - 3 = 1.

Why It Works

If start-sorted adjacent intervals are compatible, the whole list is compatible and zero removals is optimal. If the maximum start is strictly below the minimum end, every interval is active at that common time, so at most one can remain; keeping any one attains n - 1 removals. Otherwise the Boolean counter enumerates all binary keep-or-drop vectors exactly once, from all false through all true, using ordinary carry rather than a width-limited numeric mask. For each vector, the strict pair predicate rejects exactly positive-length overlaps and permits endpoint contact. Every feasible retained set appears in this enumeration, and best records the largest feasible cardinality. Removing the complement minimizes deletions because n is fixed. The preliminary checks are proven shortcuts, not assumptions about the general search.

Dry Run

Exhaustive Subsets: variable states at each step
chosen indices	vector at indices `0,1,2,3`	pair result	kept size	`best` before → after	next counter action
{}	F F F F	compatible	0	0 → 0	reset lower true entries; set index0
{0}	T F F F	compatible	1	0 → 1	reset lower true entries; set index1
{1}	F T F F	compatible	1	1 → 1	reset lower true entries; set index0
{0,1}	T T F F	compatible	2	1 → 2	reset lower true entries; set index2
{2}	F F T F	compatible	1	2 → 2	reset lower true entries; set index0
{0,2}	T F T F	compatible	2	2 → 2	reset lower true entries; set index1
{1,2}	F T T F	compatible	2	2 → 2	reset lower true entries; set index0
{0,1,2}	T T T F	compatible	3	2 → 3	reset lower true entries; set index3
{3}	F F F T	compatible	1	3 → 3	reset lower true entries; set index0
{0,3}	T F F T	conflict indices 0 and 3	2	3 → 3	reset lower true entries; set index1
{1,3}	F T F T	conflict indices 1 and 3	2	3 → 3	reset lower true entries; set index0
{0,1,3}	T T F T	conflict indices 0 and 3	3	3 → 3	reset lower true entries; set index2
{2,3}	F F T T	compatible	2	3 → 3	reset lower true entries; set index0
{0,2,3}	T F T T	conflict indices 0 and 3	3	3 → 3	reset lower true entries; set index1
{1,2,3}	F T T T	conflict indices 1 and 3	3	3 → 3	reset lower true entries; set index0
{0,1,2,3}	T T T T	conflict indices 0 and 3	4	3 → 3	carry past index3, stop
complete	counter exhausted	maximum feasible set size `3`	`3`	`3` → `3`	return `4 - 3 = 1`

Complexity Analysis

Time Complexity

O(n^2 2^n)

Space Complexity

O(n)

The general case enumerates 2^n vectors, each with O(n) counting/carry and up to O(n^2) pair checks. The preliminary copied sort costs O(n log n) and common-time test costs O(n), dominated by exponential work otherwise. The sorted outer copy, sort workspace and Boolean counter use O(n) space; input rows are read-only and no list of all subsets is stored. Counter indices avoid Java/JavaScript 32-bit shift overflow and there is no native recursion. The general method remains impractical at n = 100000; only proven fast-exit families are suitable at that bound.

Code

Solution.java

1import java.util.Arrays;2
3class Solution {4    public int eraseOverlapIntervals(int[][] intervals) {5        int n = intervals.length;6        int[][] ordered = intervals.clone();7        Arrays.sort(ordered, (x, y) -> Integer.compare(x[0], y[0]));8        boolean allCompatible = true;9        int maxStart = intervals[0][0], minEnd = intervals[0][1];10        for (int i = 0; i < n; i++) {11            if (i > 0 && ordered[i][0] < ordered[i - 1][1]) allCompatible = false;12            maxStart = Math.max(maxStart, intervals[i][0]);13            minEnd = Math.min(minEnd, intervals[i][1]);14        }15        if (allCompatible) return 0;16        // A strict common occupied time forces all but one interval to be removed.17        if (maxStart < minEnd) return n - 1;18        boolean[] chosen = new boolean[n];19        int best = 0;20        while (true) {21            int size = 0;22            for (boolean keep : chosen) if (keep) size++;23            boolean ok = true;24            for (int i = 0; i < n && ok; i++) {25                if (!chosen[i]) continue;26                for (int j = i + 1; j < n; j++) {27                    if (chosen[j] && intervals[i][0] < intervals[j][1]28                            && intervals[j][0] < intervals[i][1]) {29                        ok = false;30                        break;31                    }32                }33            }34            if (ok) best = Math.max(best, size);35            // Boolean-array carry enumerates every subset without fixed-width masks.36            int digit = 0;37            while (digit < n && chosen[digit]) chosen[digit++] = false;38            if (digit == n) break;39            chosen[digit] = true;40        }41        return n - best;42    }43}

Hints

Hint 1

Removing the fewest intervals is the same as keeping the most intervals.

Hint 2

An interval that ends early can only ever leave more room for what follows.

Hint 3

Sort by end time, keep an interval whenever its start clears the last kept end, and count everything else as removed.

Edge Cases

All identical intervals, such as three copies of [1,2], need all but one removed.
Already non-overlapping input like [[1,2],[2,3]] returns 0.
Touching endpoints never count as overlap: [1,2] and [2,3] coexist.

Common Mistakes and Interview Tips

Keeping the earliest-starting overlapping interval can block many short ones: [[0,10],[1,2],[2,3],[3,4]] needs only one removal. Prefer earliest end.
Using start > lastEnd wrongly removes touching intervals. The acceptance test is start >= lastEnd.
Updating lastEnd when removing an interval destroys the meaning of the last retained end and can cause unnecessary removals.
Enumerating masks with 1 << n overflows or wraps in Java and JavaScript at large n. The Boolean-array counter has no bit-width limit, though exhaustive search still takes exponential time.
Sorting the argument in place changes its ordering. Both approaches sort only an outer copy and never edit borrowed rows.

Key Takeaway

To keep the most intervals, always keep the one that ends first: sorting by end time makes that greedy choice available at every step.