#435
Non-overlapping Intervals
Medium Sort by end (activity selection)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the minimum number of intervals to remove so the rest don't overlap (touching ends are fine).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: remove the fewest intervals so none overlap.
Why this works: keep the interval that ends earliest; it leaves the most room for the rest.
Example: [[1,2],[2,3],[3,4],[1,3]] sorted by end
keep [1,2], [2,3], skip [1,3], keep [3,4]removed 1
✦Hints open one at a time
Equivalent: keep as many non-overlapping intervals as possible.
Activity selection: always keep the interval that ends earliest.
↗Approach
Sort by end. Keep the first; for each next interval, keep it if its start >= last kept end, otherwise remove it. Answer = number removed.
</>Solution (Java)
import java.util.*;
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // earliest end first
int removed = 0, end = Integer.MIN_VALUE;
for (int[] iv : intervals) {
if (iv[0] >= end) end = iv[1]; // keep it
else removed++;
}
return removed;
}
}!Common mistake
Sorting by start and keeping the first — a long early interval can block many short ones.
Complexity
- Time: O(n log n).
- Space: O(log n).
Topic: Greedy
🎬 Episodes 69–73: video coming soon