Merge Intervals

Problem

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

    [                     [
      [1, 3],               [1, 6],
      [2, 6],      =>       [8, 10],
      [8, 10],              [15, 18]
      [15, 18]            ]
    ]

Challenge

O(n log n) time and O(1) extra space.