Array and string patterns
Intervals
Sort first, then reason about overlap.
Understand the problem
Sort intervals by start. Maintain the end of the current merged interval. If the next start is at most that end, extend the end; otherwise emit and begin another interval.
Make it concrete
[1,4], [3,7], [9,10] merge into [1,7], [9,10].
Trade-offs and pitfalls
Closed versus half-open intervals change whether touching endpoints overlap.
Check your understanding
Explain the difference between merging intervals and selecting the maximum non-overlapping set.
Practice this topic