Non-overlapping Intervals
Understand the problem
Given a list intervals, each being [start, end]. Return the minimum number of intervals you must remove so that the remaining intervals do not overlap.
Example:
intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
// removing [1, 3] is enough → [1,2],[2,3],[3,4] remain, none overlapping
output = 1Two intervals that touch at the edge ([1,2] and [2,3]) do NOT count as overlapping.
Optimal solution
O(n log n) time, O(1) spacefunction eraseOverlapIntervals(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]) // by END ascending
let prevEnd = -Infinity
let removed = 0
for (const [start, end] of intervals) {
if (start >= prevEnd) {
prevEnd = end // no overlap → keep this interval
} else {
removed++ // overlap → drop (the one that ends later)
}
}
return removed
}The optimal solution uses a greedy trick: sort by END point and always keep the interval that ends earliest, since it "leaves the most room" for later intervals.
When you meet an interval that starts before prevEnd (an overlap), remove that one — it ends later (because of the sort by end), so keeping it would only hurt.
Step-by-step trace
1function eraseOverlapIntervals(intervals: number[][]): number {2 intervals.sort((a, b) => a[1] - b[1]) // by END ascending3 let prevEnd = -Infinity4 let removed = 05 for (const [start, end] of intervals) {6 if (start >= prevEnd) {7 prevEnd = end // no overlap → keep this interval8 } else {9 removed++ // overlap → drop (the one that ends later)10 }11 }12 return removed13}Edge cases to remember
Touching edges
[1,2]and[2,3]: usestart >= prevEnd(the ≥ sign) so they count as NOT overlapping — using>would remove one by mistake.All intervals identical ([[1,2],[1,2],[1,2]]) → keep 1, remove n−1.
An empty list or 1 interval → return 0.
Sorting by START instead of END is the classic trap: with [[1,100],[2,3],[3,4]], sorting by start keeps [1,100] and removes the 2 small intervals — wrong.
You must sort by end.