Merge Overlapping Intervals

Each interval is a pair [start, end] with start <= end. Write merge_intervals(intervals) that merges every group of overlapping intervals and returns the result as a list of [start, end] lists, sorted by start.

Intervals that only touch also merge: [1, 3] and [3, 5] become [1, 5]. The input can be in any order.

Examples

merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]])
# returns [[1, 6], [8, 10], [15, 18]]

merge_intervals([[1, 4], [4, 5]])
# returns [[1, 5]]

merge_intervals([[5, 7], [1, 2]])
# returns [[1, 2], [5, 7]]

In the first example [1, 3] and [2, 6] overlap, so they merge into [1, 6].

Constraints

• 0 <= len(intervals) <= 10,000
• -10**6 <= start <= end <= 10**6