Interview challenge · medium · array, intervals, sorting
Merge Intervals
The challenge
Given a list of intervals [start, end], merge all the ones that overlap and return the resulting list, sorted by start. Intervals that only touch ([1, 4] and [4, 5]) count as overlapping.
Example
[[1, 3], [2, 6], [8, 10], [15, 18]] -> [[1, 6], [8, 10], [15, 18]]
[[1, 4], [4, 5]] -> [[1, 5]]Idea: sort by start. After sorting, anything that overlaps the interval you are building has to be the next one in the list, so a single pass is enough: either extend the last merged interval or start a new one. Time O(n log n) for the sort, then O(n).
The solution
# Merge Intervals - ayotl.dev
def merge(intervals):
out = []
# after sorting, overlaps are neighbors
for s, e in sorted(intervals):
if out and s <= out[-1][1]:
# overlaps: extend the last one
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out
print(merge([[1, 3], [2, 6], [8, 10],
[15, 18]]))
print(merge([[1, 4], [4, 5]]))
$ python3 merge_intervals.py
[[1, 6], [8, 10], [15, 18]]
[[1, 5]]