Practice: Merge Intervals
Sort first, then sweep.
A calendar has meetings from one to three, two to six, eight to ten, and nine to twelve. Some overlap. Merge the overlapping ones, so you can see when you're really busy. Pause. What would make this easy?

- Meetings that overlap
- Merge them
- What makes it easy?
Sort, then sweep
Sort the meetings by start time. Then sweep through them. If a meeting starts before the last merged one ends, they overlap, so we stretch the end. Otherwise, it starts a new block. Run it. One to six, and eight to twelve. Sorting is O of N log N, and the sweep is O of N.
def merge_intervals(meetings):
meetings.sort(key=lambda m: m[0])
merged = [meetings[0]]
for start, end in meetings[1:]:
last = merged[-1]
if start <= last[1]:
last[1] = max(last[1], end)
else:
merged.append([start, end])
return merged
print(merge_intervals([[8, 10], [1, 3], [9, 12], [2, 6]]))[[1, 6], [8, 12]]
Sorting as step one
Many tricky problems become simple once the data is sorted. Overlapping meetings, finding pairs, removing duplicates, and finding gaps. If a problem feels hard, ask yourself, would it be easier if this was sorted? The answer is often yes.
| key | value |
|---|---|
| Overlaps | sort by start |
| Pairs | sort, then two pointers |
| Duplicates | sort, compare neighbours |
| Ask | would sorted help? |
Summary
Sort by start time, then sweep and merge overlaps. Sorting first turned a messy problem into one simple pass. Next, a sorting quiz.
Key takeaways- Sort by start
- Overlap? Stretch the end
- O(n log n)