Deviopath › Python

Merge Overlapping Intervals

Hard · Sorting

An interval [start, end] covers every number from start to end. Two intervals overlap when one starts before (or exactly when) the other ends, like [1, 4] and [4, 5].

The trick: sort the intervals by start. Then each interval either overlaps the last merged one (extend its end) or starts a new group.

Write merge_intervals(intervals) that merges all overlapping intervals and returns them sorted by start. The input is not sorted and may be empty. Every interval has start <= end.

Next: Roman Numerals Both Ways