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: max is what makes the merge handle containment without a special case. When [1, 10] is followed by [2, 3], extending with block.end = max(10, 3) leaves the block untouched — exactly right, because the second interval is entirely swallowed. A naive block.end = next.end would 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.

---

The one-line idea: 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 the inputs are already sorted lists, a two-pointer walk beats sorting them together.

---

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. The common refinement for large inputs is to merge the per-employee schedules with a heap rather than pooling and sorting everything, which is O(n log k) for k employees instead of O(n log n).

3. Two sorted lists need no sort

Meeting Scheduler gives two people's free slots, each already sorted. Sorting them together throws that away. Instead walk both with an index each:

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

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 free stretches fell 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 Employee Free Time exactly.
• 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. 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 sorted lists of free intervals. Two pointers, advancing whichever interval ends first.
Pattern: two-pointer intersection of sorted lists. Target: O(m + n) time, O(1) space.

▶ Employee Free Time

Time free for every employee. Pool and merge all busy intervals — or merge with a heap for large inputs — then emit the gaps.
Pattern: merge, then take the complement. Target: O(n log n), or O(n log k) with a heap.

---

7. Common pitfalls 🚫

• Assigning end = next.end instead of max. Containment silently shrinks the block.
• Not deciding the endpoint convention. Whether touching intervals merge changes the answer, and problems differ.
• Sorting already-sorted lists together. Meeting Scheduler is O(m + n); sorting makes it O((m+n) log(m+n)) for nothing.
• 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

1. Sort by start. It is the decision that removes most of the case analysis.
2. Extend with max, which handles containment for free.
3. Free time is the complement of merged busy time — no second algorithm.
4. Already sorted? Use two pointers. Advance whichever interval ends first.
5. Overlap is [max(starts), min(ends)] — worth memorising as a formula.
6. State the endpoint convention before writing the comparison.
7. 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.