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.