Merge Intervals

Given a list of intervals, merge all overlapping ones and return the result.

Example

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

Approach

Sort by start value first — once sorted, any interval that overlaps the one before it must have a start that's less than or equal to the previous interval's end. Sweep once, extending the last merged interval's end whenever the next one overlaps, or starting a new merged interval otherwise.

Walkthrough

1intervals.sort()
2merged = []
3for start, end in intervals:
4    if merged and start <= merged[-1][1]:
5        merged[-1][1] = max(merged[-1][1], end)
6    else:
7        merged.append([start, end])

Input format

Line 1: number of intervals R Next R lines: start end

Print the merged intervals, one start end pair per merged interval, separated by |.