Non-overlapping Intervals (LC 435)

Pattern: Intervals — greedy by end time
Difficulty: Medium
Key Concept: To fit maximum non-overlapping intervals, always keep the interval that ends earliest—it leaves the most room for the future.

Problem Statement

Given an array of intervals intervals[i] = [start_i, end_i], return the minimum number of intervals you must remove so that the rest are mutually non-overlapping.

Note: Intervals that only touch at an endpoint do not count as overlapping (e.g. [1,2] and [2,3] can both stay). They overlap only if they share an open overlap (e.g. [1,3] and [2,4]).

Input: list of intervals.
Output: int removals.

Examples:

• [[1,2],[2,3],[3,4],[1,3]] → 1 (remove [1,3]).
• [[1,2],[1,2],[1,2]] → 2.
• [[1,2],[2,3]] → 0.

---

1. Algorithm & Pseudocode

Brute force

1. Try all subsets of intervals, check non-overlap, maximize size—exponential.
2. Or DP by sorting on one coordinate—O(n^2).

Pseudocode (subset):

best = 0
for each subset S of intervals:
    if S is non-overlapping: best = max(best, |S|)
return n - best

Optimal (greedy)

1. Sort by end ascending (if tie, by start).
2. Keep prevEnd = end of last chosen interval; count = 0 non-overlap kept (or count removals).
3. For each interval: if start >= prevEnd, keep it, set prevEnd = end. Else remove (increment removal counter).
4. Alternatively: count kept k, answer n - k.

Pseudocode:

sort by end
kept = 0
prevEnd = -infinity
for [s,e] in intervals:
    if s >= prevEnd:
        kept++
        prevEnd = e
return n - kept

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why sort by end: Picking the interval that finishes soonest minimizes conflict with future starts—classic “activity selection.”

Why not sort by start: Long early interval can block many short ones that would fit after it.

Removals vs kept: min removals = n - (max non-overlapping subset size).

---

3. The Dry Run

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

interval	s >= prevEnd?	action	prevEnd	kept
[1,2]	yes (-∞)	keep	2	1
[1,3]	no (1 < 2)	remove	2	1
[2,3]	yes (2 >= 2)	keep	3	2
[3,4]	yes	keep	4	3

Kept = 3, n = 4 → removals = 1.

---

4. Java Solution

Brute Force

import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        int best = 0;
        // Try all masks 0..2^n-1 (only for tiny n; illustrative brute force)
        for (int mask = 0; mask < (1 << n); mask++) {
            if (nonOverlapping(intervals, mask, n)) {
                best = Math.max(best, Integer.bitCount(mask));
            }
        }
        return n - best;
    }

    private boolean nonOverlapping(int[][] intervals, int mask, int n) {
        int[][] chosen = new int[n][];
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) {
                chosen[k++] = intervals[i];
            }
        }
        Arrays.sort(chosen, 0, k, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 1; i < k; i++) {
            if (chosen[i][0] < chosen[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
}

Time: O(2^n × n log n). Space: O(n). (Educational only.)

Optimal

import java.util.Arrays;

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

Time: O(n log n). Space: O(1) extra besides sort.

---

5. The “Java vs. Others” Edge

• Integer.MIN_VALUE as sentinel works for prevEnd if intervals fit in int; alternatively use first interval after sort.
• Comparator on a[1] is the whole trick—pair with eraseOverlapIntervals sibling problem “maximum non-overlapping” by returning kept.
• For floating intervals, same greedy with double ends.

---

6. Complexity Summary

Approach	Time	Space	Notes
Subset enumeration	O(2^n × n log n)	O(n)	Not scalable
DP on sorted starts	O(n^2)	O(n)	When greedy not valid—different problems
Greedy by end	O(n log n)	O(1)	Standard for this problem