Merge overlapping time ranges

DSA, Medium

Which structure or algorithm, and what does it cost.

You get a list of closed ranges [start, end] with start <= end. Two ranges overlap if they share at least one point, so [1,4] and [4,5] overlap. Return the smallest list of non-overlapping ranges that covers exactly the same points, sorted by start. The input is not sorted.

Examples

Input [[1,3],[2,6],[8,10],[15,18]]

Output [[1,6],[8,10],[15,18]]

Why because [1,3] and [2,6] overlap.

Input [[1,4],[4,5]]

Output [[1,5]]

Why because they share the point 4.

Input [[1,10],[2,3]]

Output [[1,10]]

Why because the second range lies inside the first.

Constraints

0 <= number of ranges <= 100,000.
-1,000,000,000 <= start <= end <= 1,000,000,000.

Your answer must contain

The method and why it is correct; code; time and memory; a hand trace of example 1.