Free lessonsIntervals · Stage 0 · Overlap and merge · Step 3

Merge a whole list

Sort by start, then walk once, either stretching the last merged interval or starting a new one. About 12 minutes.

Extend or start fresh

Walk the sorted list keeping a result list, like a person tidying a timetable. For each interval, look at the last merged one. If the new start is at or before its end, stretch that end to the larger of the two ends.

If not, there is a gap, so add the interval as a new group.

Starts before the open group ends? stretch its end to the larger end.

Otherwise: a gap: add the interval as a new group.

In code

merged = []
for start, end in sorted(intervals):
    if merged and start <= merged[-1][1]:
        last = merged[-1]
        last[1] = max(last[1], end)
    else:
        merged.append([start, end])
return merged

intervals = [[8, 10], [1, 3], [2, 6], [9, 12]]

Sort by start: [1, 3], [2, 6], [8, 10], [9, 12]. Start the answer with [1, 3].

Move 1 of 4

Trace it

Sorted: [1, 3], [2, 6], [8, 10], [9, 12]. Start with [1, 3]. Next, 2 starts before 3 ends, so it stretches to [1, 6]. Then 8 starts after 6, a gap, so add [8, 10]. Then 9 starts before 10 ends, so it stretches to [8, 12].

Result: [[1, 6], [8, 12]].

Take the larger end: [1, 10] then [2, 3] must stay [1, 10].

One pass: each interval is looked at once after the sort.

Quick check

After sorting, the list is [1, 5], [2, 3], [4, 7]. What is the merged result?

A[[1, 7]]
B[[1, 5], [4, 7]]
C[[1, 3], [4, 7]]

Show the answer

[[1, 7]]. [2, 3] fits in [1, 5]. Then 4 <= 5, so the group stretches to 7.

Your problem

Merge a whole list

A shared calendar holds bookings as intervals [start, end], both ends included, in no particular order. Merge every group of overlapping bookings into one interval and return the result sorted by start.

Example

intervals = [[8, 10], [1, 3], [2, 6], [9, 12]] → [[1, 6], [8, 12]]

0 ≤ intervals.length ≤ 10,000 · 0 ≤ start ≤ end ≤ 1,000,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding