</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Merge intervals loop and the two-pointer free-time variant

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.


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:

Merged busy blocks with the gaps between them as free time

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]]

Interval merging worked example

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.end instead of max. 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

  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. Two lists of disjoint slots? Sort each, then 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.

Merge Intervals

Core idea: You get a bag of intervals in no particular order and must fuse every group that overlaps. The hard part is finding which intervals overlap, because any two of them could touch, and comparing all pairs is O(n²). Sort by start time first. Once the intervals are ordered by where they begin, any interval that overlaps the current block must come right after it, so one left-to-right sweep is enough. Keep one "current" merged interval. If the next interval starts at or before the current end (next.start <= current.end), extend with current.end = max(current.end, next.end). Otherwise the current block is finished: emit it and start a new one. The sort dominates at O(n log n); the sweep is O(n).


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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.