Pattern Recognition Drill
Medium Greedy
The Problem
Minimum intervals to remove so the rest don't overlap.
What approach would you use?
Think about it before scrolling down.
Sort by end time. Keep intervals that don't overlap with the last kept. Remove count = total - kept. O(n log n).
LIS-like DP on intervals sorted by end. O(nĀ²) ā much slower than greedy.
Common Trap
Sort by END time, not start time. Sorting by start doesn't give the optimal greedy choice.