Non-overlapping Intervals
Remove the minimum number of intervals to eliminate overlaps.
Pattern fit
Keeping the interval with the smallest end preserves the most room for future intervals, which is the standard interval-scheduling greedy proof.
Key observation
When intervals overlap, the later-ending one is the worse candidate to keep.
Target complexity
O(n log n) / O(1)
How to break down the solution cleanly
Keeping the interval with the smallest end preserves the most room for future intervals, which is the standard interval-scheduling greedy proof.
When intervals overlap, the later-ending one is the worse candidate to keep.
Identify the local choice that seems to preserve the most future flexibility.
Sort or preprocess if that makes the choice testable.
Reference implementation
Python# Generic pattern template
items.sort(key=priority)
answer = 0
for item in items:
if can_take(item):
take(item)
answer = update(answer)
Common pitfalls
Sorting by start time but not using the right keep/remove rule.
Counting kept intervals but forgetting the final conversion to removals.
Common follow-ups
Why is earliest end the safe greedy choice?
How does this relate to merge intervals?
Continue with related problems
Build repeatable depth inside the Greedy cluster before moving on.