mycsmajor
Data structures problem 18 of 30

Merge intervals

  • Data structures
  • Medium

Write merge_intervals(intervals) that merges all overlapping [start, end] intervals. Intervals that touch, like [1, 4] and [4, 5], count as overlapping.

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

merge_intervals([[1, 4], [4, 5]])
# [[1, 5]]
Show hint

Sort by start time first. Then each interval either overlaps the last merged one or starts a new one.

Show solution 
def merge_intervals(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

After sorting, an interval can only overlap the most recent merged one. max handles an interval completely inside another, like [1, 10] and [2, 3]. Sorting dominates, so it is O(n log n). Calendars and booking systems use exactly this.

Want a problem like this every day? See today's problem and keep a streak going.