Non-overlapping Intervals
Find the minimum number of intervals to remove so that the rest do not overlap.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Sort by end time and keep every interval that starts after the last kept one ends; each overlapping interval is a removal.
Pattern: Greedy & intervals. Make the locally best choice, usually after sorting, and argue why it never hurts later.
Complexity
| Measure | Bound |
|---|---|
| Time | O(n log n) |
| Extra space | O(1) extra, excluding sorting |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.