Pattern Recognition Drill
Medium Intervals
The Problem
Given a collection of intervals, merge all overlapping intervals.
What approach would you use?
Think about it before scrolling down.
Sort by start. If current overlaps last merged, extend end. Else start new. O(n log n).
Same approach. Sort is the bottleneck at O(n log n); merge is O(n).
Common Trap
After sorting, compare with the LAST merged interval, not the previous input interval.