Problem - Merge Intervals

Given a list of intervals, merge all overlapping intervals.

Example: [[1,3], [2,6], [8,10], [15,18]] becomes [[1,6], [8,10], [15,18]]. The [1,3] and [2,6] overlap, so they merge to [1,6]. Before reading the solution, think: what sort order helps you merge efficiently?

Constraint: $n \le 10^4$. Sorting by start time gives you $O(n \log n)$ time using $O(n)$ space instead of checking all $O(n^2)$ pairs.