Non-overlapping Intervals
The problem
Remove the fewest intervals so the remaining intervals never overlap. Here an interval ending at time t does not conflict with one starting at t. Each interval has start < end.
Example
[[1, 3], [2, 4], [3, 5]] → 1 removal
Need a hint?
Keeping the interval that finishes earliest leaves the most room.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Sort by end time. Greedily keep each interval whose start is at least the last kept end, then update that end. Count rejections, or subtract the kept count from the original total. Initialize so the first interval is always considered.
Complexity
O(n log n) time; sorting determines auxiliary space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.