Merge and Free Time
What is this?
Two people compare calendars to find a free hour. Nobody does this by checking every pair of meetings against every other. You lay both calendars out in time order and walk down them together. Sorting is what makes that walk possible, and it is the single decision that collapses interval problems from fiddly case analysis into one clean sweep.
Once busy time is merged, free time needs no algorithm at all. It is whatever is left.
Fun fact:
maxis what makes the merge handle containment without a special case. When[1, 10]is followed by[2, 3], extending withblock.end = max(10, 3)leaves the block untouched, exactly right, because the second interval is entirely swallowed. A naiveblock.end = next.endwould shrink the block to 3 and silently lose seven units of busy time, and the bug only shows up on inputs where one meeting sits inside another.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
In short: sort by start, then either extend the current block or emit it and begin a new one. Free time is the complement of the merged blocks, and when you have two lists of disjoint slots, sorting each list on its own and walking both with two pointers beats pooling and re-merging them.
1. The merge sweep
intervals.sort(key=lambda x: x[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # extend; max handles containment
else:
merged.append([start, end])
Whether the comparison is <= or < is the endpoint convention, and it must be a deliberate choice: with <=, the intervals [1,3] and [3,5] merge into [1,5]; with <, they stay separate. Both are defensible, and problems specify one or the other. State your assumption before you write it.
2. Free time is the complement
Once every person's busy intervals are pooled and merged, the free stretches are simply the gaps:
No extra logic is needed, walk the merged list and emit [previous.end, current.start] whenever there is a positive gap. Each employee's list is already sorted, so for many intervals and few employees you can k-way merge the per-employee schedules with a heap instead of pooling and sorting everything. That is O(n log k) time and O(k) heap space for k employees, against O(n log n) time and O(n) space for pooling.
3. Two lists of disjoint slots: sort each, then walk both
Meeting Scheduler gives two people's free slots. Each person's own slots are disjoint, but the lesson does not assume the list is in order, so sort each list by start first (a copy of each, O(n log n + m log m)). Do not pool them into one list and merge: the two-pointer walk is what finds the overlaps. Then walk both with an index each:
a, b = sorted(a), sorted(b)
i = j = 0
while i < len(a) and j < len(b):
start = max(a[i][0], b[j][0]) # the overlap begins at the later start
end = min(a[i][1], b[j][1]) # and ends at the earlier end
if end - start >= duration:
return [start, start + duration]
if a[i][1] < b[j][1]: # advance whichever ends first;
i += 1 # it cannot overlap anything later
else:
j += 1
return []
The overlap of two intervals is always [max(starts), min(ends)], and advancing the one that ends first is safe because it can never intersect any later interval on the other side.
4. A 30-second worked example
intervals = [[1,3], [2,6], [8,10], [15,18]]
The merged blocks are [1,6], [8,10] and [15,18], so the free stretches are [6,8] and [10,15]. They fall out of the merged list without a single extra comparison.
5. Where you'll actually meet this
- Calendar and scheduling software. Free/busy lookup across several attendees is the Employee Free Time problem.
- Resource booking. Detecting double-bookings for rooms, vehicles or equipment.
- Genomics. Merging overlapping read alignments before computing coverage.
- Log and trace analysis. Collapsing overlapping spans into consolidated activity periods.
- Billing and rostering. Consolidating overlapping shifts or usage windows before invoicing.
6. Problems in this chapter
Merge Intervals
Merge all overlapping intervals, where touching intervals count as overlapping. Sort by start, extend with max, emit on a gap.
Pattern: sort-and-sweep merge. Target: O(n log n) time, O(n) space.
Meeting Scheduler
Earliest slot of a given duration free for both people, given two lists of free intervals (disjoint within each person, not necessarily in order). Sort each list, then two pointers, advancing whichever interval ends first.
Pattern: sort, then two-pointer intersection. Target: O(n log n + m log m) time, O(n + m) space (the sorts copy; sorting in place would make the extra space O(1)).
Employee Free Time
Time free for every employee. Pool and merge all busy intervals, or k-way merge the per-employee lists with a heap, then emit the gaps.
Pattern: merge, then take the complement. Target: O(N log N) time and O(N) space pooled, or O(N log K) time and O(K) heap space with a heap (output extra).
7. Common pitfalls
- Assigning
end = next.endinstead ofmax. Containment silently shrinks the block. - Not deciding the endpoint convention. Whether touching intervals merge changes the answer, and problems differ.
- Pooling the two schedules instead of walking them. In Meeting Scheduler, sort each list separately and use two pointers; the sweep itself is
O(m + n). - Assuming the input is sorted. Merge Intervals arrives unsorted, and Meeting Scheduler does not promise order, so sort first. Only the Employee Free Time per-employee lists are given sorted.
- Advancing the wrong pointer. Advance the interval that ends first; the other may still overlap something later.
- Emitting zero-length gaps. Adjacent merged blocks produce an empty free interval that should be filtered out.
- Forgetting empty input. No intervals means no merged blocks and no free time, not a crash.
- Sorting by end time. It works for "maximum non-overlapping intervals" but not for merging, different problem, different key.
8. Key takeaways
- Sort by start. It is the decision that removes most of the case analysis.
- Extend with
max, which handles containment for free. - Free time is the complement of merged busy time, no second algorithm.
- Two lists of disjoint slots? Sort each, then use two pointers. Advance whichever interval ends first.
- Overlap is
[max(starts), min(ends)], worth memorising as a formula. - State the endpoint convention before writing the comparison.
- Why interviewers like it: everyone understands calendars, so the problem statement takes ten seconds and the remaining time is entirely about how carefully you handle the boundaries.
Order: Merge Intervals, Meeting Scheduler, Employee Free Time.
Employee Free Time
Core idea: Each employee hands you a sorted list of busy intervals, and you want the windows where nobody is busy. Stop thinking per employee. Whether a meeting belongs to Alice or to Bob doesn't matter: a moment is free only if it sits outside every busy block. So flatten all busy intervals into one pile, sort by start, and merge overlaps exactly as you would for a single calendar. What's left is a non-overlapping sequence of "somebody is busy" blocks, and the gaps between consecutive merged blocks are the moments when everyone is free. The sort dominates: O(N log N), where N is the total number of intervals.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson