LeetCode · #435

Non-overlapping Intervals Solution

Return the minimum number of intervals to remove so the rest are non-overlapping.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #435

🏗️

Pattern

Intervals — greedy sort by end

Given array of intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping.

Example

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1 // Remove [1,3]. Remaining: [1,2],[2,3],[3,4] — non-overlapping.

Constraints

• 1 ≤ intervals.length ≤ 10⁵ • intervals[i].length == 2 • -5 × 10⁴ ≤ startᵢ < endᵢ ≤ 5 × 10⁴

Section Two · Approach 1

DP — O(n²)

Sort by start. dp[i] = max non-overlapping intervals ending at i. For each i, check all j < i.

Problem: O(n²). The classic interval scheduling greedy: sort by end time, greedily keep the earliest-ending non-overlapping interval. Removals = total − kept.

Java — Greedy (sort by end — this IS optimal)

 import java.util.*;
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
int kept = 1, end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
                kept++;
                end = intervals[i][1];
            }
        }
return intervals.length - kept;
    }
}

Python — Greedy (sort by end)

 class Solution:
def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        kept, end = 1, intervals[0][1]
for s, e in intervals[1:]:
if s >= end:
                kept += 1
end = e
return len(intervals) - kept

Section Three · Approach 2

Greedy Sort-by-End — O(n log n)

Sort by end time. Greedily keep each interval whose start ≥ the last kept interval's end. The number of intervals NOT kept = removals needed.

💡 Mental model: This is the classic activity selection problem from greedy algorithms. Imagine scheduling as many meetings as possible in one room. Sort by end time. Always pick the meeting that finishes earliest and doesn't conflict. This maximizes the number of meetings (= minimum removals).

Algorithm

Sort intervals by end ascending.
Initialize kept = 1, end = intervals[0].end.
For each interval: if start >= end → keep it, update end. Else skip (removed).
Return n - kept.

🎯 When to recognize this pattern: "Minimum removals to make intervals non-overlapping" = "Maximum non-overlapping intervals you can keep." This is interval scheduling maximization. Always sort by end (not start!). The exchange argument proves greedy correctness: earliest-ending intervals leave the most room for future selections.

Why sort by end, not start? Sorting by start groups intervals that begin together but may have vastly different lengths. Sorting by end selects the interval that finishes earliest — freeing the timeline for more intervals. [1,100] starts early but hogs the timeline; [1,2] ends early and is a better greedy choice.

Section Four · Trace

Visual Walkthrough

Trace for intervals = [[1,2],[2,3],[3,4],[1,3]].

Non-overlapping Intervals — Sort by End

Section Five · Implementation

Code — Java & Python

The brute force section already contains the optimal greedy code (it IS the clean approach). See Section 02 for complete Java and Python implementations.

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DP (LIS-variant)	O(n²)	O(n)	dp[i] = max chain ending at i
Greedy sort-by-end ← optimal	O(n log n)	O(1)	Classic activity selection; single pass after sort

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No overlap	`[[1,2],[3,4]]`	Remove 0.
All overlap	`[[1,4],[2,3],[3,5]]`	Keep [2,3] and [3,5]. Remove 1.
Single interval	`[[1,2]]`	Remove 0.
Touching	`[[1,2],[2,3]]`	start=end → not overlapping. Remove 0.
Negative values	`[[-2,0],[0,2]]`	Works the same. Sort + greedy.

⚠ Common Mistake: Sorting by start instead of end. Sorting by start and greedily keeping the first non-overlapping interval does NOT maximize the number kept. Example: [[1,100],[2,3],[3,4]]. Sort by start: keep [1,100], skip rest → kept=1. Sort by end: keep [2,3],[3,4] → kept=2. Removing 1 is better than removing 2.

← Back to Interval problems

LearningTree

LC 435 · Non-overlapping Intervals — Solution & Explanation | DSA Guide