Interval Merging with Sorted Sweep

Problem

Merge all overlapping intervals.

intervals is a list of [start, end] pairs. Sort by start, then extend the current merged interval while the next start is at most the current end; touching intervals such as [1,4] and [4,5] merge.

Return the merged intervals sorted by start.

Hint

After sorting by start, only the end of the last merged interval matters.

Test cases

case 1

in: [[[1,3],[2,6],[8,10],[15,18]]]

expected: [[1,6],[8,10],[15,18]]

case 2

in: [[[1,4],[4,5]]]

expected: [[1,5]]

case 3

in: [[[1,2]]]

expected: [[1,2]]

case 4

in: [[]]

expected: []

case 5

in: [[[5,6],[1,2],[2,3]]]

expected: [[1,3],[5,6]]

Starter codePython

def merge_intervals(intervals):
    # Your code here
    pass

5 test cases · run your code against them in the editor