Merge Intervals
Merge all overlapping intervals and return the non-overlapping intervals that cover the same ranges.
A way to picture it
Lay out everyone's vacation dates on a wall calendar in order of when they start. Now walk left to right with a marker: if the next trip starts before your current stretch ends, just extend the stretch. Otherwise, lift the marker and start a new one.
How to approach it
Sort by start. Each interval can only overlap the last interval you placed — extend it, or start a new one.
Example
Input: {"intervals":[[1,3],[2,6],[8,10],[15,18]]}. Output: [[1,6],[8,10],[15,18]].
Complexity: O(n log n) time and O(n) space. Sorting dominates; the merge itself is one pass.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.