Merge overlapping intervals
Each item of intervals is a pair [start, end] with start ≤ end. It stands for every number from start to end, both ends included. Two intervals overlap when they share at least one number, so [1, 3] and [3, 5] overlap at 3, but [1, 2] and [3, 4] do not.
Intervals that overlap, directly or through a chain of others, form a group. Replace each group with one interval that runs from the group's smallest start to its largest end. An interval that overlaps nothing is a group of one and stays as it is. Return the new intervals as a list of [start, end] lists, sorted by start. The input can come in any order.
intervals = [[1, 4], [2, 5], [7, 9]]Output[[1, 5], [7, 9]][1, 4] and [2, 5] share 2 through 4, so they become [1, 5]. [7, 9] shares nothing.
intervals = [[6, 8], [1, 3], [2, 4]]Output[[1, 4], [6, 8]]The input is not sorted. [1, 3] and [2, 4] overlap; [6, 8] stands alone.
intervals = [[1, 3], [3, 5]]Output[[1, 5]]They share the number 3, so they count as overlapping.
1 ≤ len(intervals) ≤ 105
0 ≤ start ≤ end ≤ 105
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.