Given two people’s busy intervals and working hours, find the time when both are free. How is it the merge-intervals problem in disguise?
Predict first
What shared free slots does the merge-and-gap method print?
import Foundation
func hm(_ m: Int) -> String { String(format: "%d:%02d", m / 60, m % 60) }
func commonFree(_ a: [[Int]], _ b: [[Int]], day: [Int]) -> [[Int]] {
var busy: [[Int]] = []
for iv in (a + b).sorted(by: { $0[0] < $1[0] }) { // merge both people's busy time
if let last = busy.last, iv[0] <= last[1] { busy[busy.count - 1][1] = max(last[1], iv[1]) } else { busy.append(iv) }
}
var free: [[Int]] = [], cursor = day[0]
for iv in busy {
if iv[0] > cursor { free.append([cursor, min(iv[0], day[1])]) } // a gap before this meeting
cursor = max(cursor, iv[1])
if cursor >= day[1] { break }
}
if cursor < day[1] { free.append([cursor, day[1]]) }
return free
}
let alice = [[9 * 60, 10 * 60 + 30], [12 * 60, 13 * 60], [16 * 60, 18 * 60]]
let bob = [[10 * 60, 11 * 60 + 30], [12 * 60 + 30, 14 * 60 + 30], [14 * 60 + 30, 15 * 60], [16 * 60, 17 * 60]]
for f in commonFree(alice, bob, day: [9 * 60, 18 * 60]) { print("free \(hm(f[0]))-\(hm(f[1]))") }
print(commonFree([[0, 100]], [[0, 100]], day: [0, 100]))
print(commonFree([], [], day: [540, 600]))- free 11:30-12:00 / free 15:00-16:00 / [] / [[540, 600]]
- free 11:00-12:00 / free 15:00-16:00 / [] / []
- free 11:30-12:00 / free 15:00-16:00 / [[0, 100]] / [[540, 600]]
Mental model. Two people paint their busy hours on the same strip of paper; the unpainted stretches inside the working day are the times you can both meet.
“Both free” is “neither busy”, so combine both busy lists, sort by start, and merge overlapping ones (the sweep from the intervals question). The gaps between the merged busy blocks, clipped to the working day, are the shared free time. Walk the merged blocks with a cursor that starts at the beginning of the day: if the next block starts after the cursor, the gap is free; move the cursor to the larger of itself and the block’s end; stop when the cursor reaches the end of the day, and add the final gap if any remains. O((n + m) log(n + m)) for the sort; if both lists are already sorted a two-pointer merge makes it linear.
Use a convenient unit (minutes since midnight) and format at the end. The check merges two people into busy blocks of 9:00–11:30, 12:00–15:00 and 16:00–18:00, giving free slots of 11:30-12:00 and 15:00-16:00. Edge cases to spell out: touching meetings (14:30 end and 14:30 start leave no gap), meetings outside working hours, nobody busy (the whole day is free), everyone busy all day ([]), and time zones, which you normalise to one before merging. Reported at Google (anonymous, unverified); with more than two people the same code works on the concatenation of all lists.
Merged busy time is 9:00–11:30, 12:00–15:00 and 16:00–18:00; full overlap leaves nothing, and no meetings leave the whole day.
Common traps
- Comparing the two lists pairwise by hand. It is longer and error prone; merge first.
- Forgetting the part after the last meeting or before the first one.
They might follow up with
- How do you find a slot of at least 30 minutes? Filter the gaps by length after computing them.
- How would this change for ten people? Concatenate all busy lists and run the same merge.
Related questions
- 29.1.2 Merge overlapping intervals: [[1,3],[8,10],[2,6],[15,18]] becomes [[1,6],[8,10],[15,18]]. How do you do it…
- 29.2.7 Given function entry and exit events with timestamps, print the time spent in each function when it exits.…
- 29.2.9 Find the longest run in a float array where adjacent chosen values differ by at most 1. Why must you ask…
← Given function entry and exit events with timestamps, print the time… Find the longest run in a float array where adjacent chosen values… →