Medium · Interval Merge
Understand → Visualise → Practice.
Sorting by start time makes every interval that can overlap the current merged block arrive before any later separate block.
If the next start is at most the current end, extend the end; otherwise begin a new output interval.
Order by start.
Extend current end to max of both ends.
Append a new current interval.
O(n log n) time and O(n) output space.
When intervals overlap, use the larger end; the next interval may be fully contained.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.