Find Common Free Time Slots Across Calendars
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Find Common Free Time Slots Across Calendars
You are building a scheduling assistant on top of a shared calendar product. Each participant has a list of **busy** time intervals for a given day. You need to find every window during which **all** participants are simultaneously free and that is long enough to hold a meeting.
All times are integers on a single timeline (for example, minutes elapsed since midnight). Intervals are half-open: a busy interval `[start, end)` means the participant is busy from `start` up to but not including `end`, so a meeting may begin exactly at the moment another booking ends.
Write a function that, given:
- `day_start` and `day_end` (integers, `day_start < day_end`) defining the bookable working window `[day_start, day_end)`,
- `schedules`: a list of participants, where each participant is a list of busy intervals `[start, end)` (intervals for a single participant may be given in any order and may overlap or touch each other), and
- `duration` (a positive integer): the minimum required meeting length,
returns the list of **maximal** time windows, clipped to `[day_start, day_end)`, during which **every** participant is free and whose length is **at least** `duration`. Return the windows as `[start, end)` pairs sorted in ascending order of `start`. If no such window exists, return an empty list.
### Notes and edge cases
- A participant with no busy intervals is free for the entire working window.
- Busy intervals may extend outside `[day_start, day_end)`; only the portion inside the working window matters.
- Adjacent free windows separated only by a touching busy interval should not be merged across that busy interval — a window must be a contiguous span where no participant is busy.
- "Maximal" means you should not return a window that is strictly contained in another free window; extend each free window as far left and right as possible before clipping to the working window and applying the `duration` filter.
### Example
```
day_start = 540 # 9:00 AM
day_end = 1080 # 6:00 PM
schedules = [
[[600, 660], [780, 840]], # person A: busy 10:00-11:00, 13:00-14:00
[[540, 600], [900, 960]] # person B: busy 9:00-10:00, 15:00-16:00
]
duration = 60
# Combined busy (union): [540,600), [600,660), [780,840), [900,960)
# -> merged busy: [540,660), [780,840), [900,960)
# Free windows inside [540,1080): [660,780), [840,900), [960,1080)
# Lengths: 120, 60, 120 -> all >= 60
# Output: [[660, 780], [840, 900], [960, 1080]]
```
If `duration` were `90`, the window `[840, 900)` (length 60) would be dropped, giving `[[660, 780], [960, 1080]]`.
Quick Answer: This question evaluates a candidate's ability to work with interval merging and sweep-line techniques over multiple overlapping schedules. It tests practical coding skill in handling edge cases like half-open intervals, boundary touching, and multi-way set intersection, a common pattern in coding and algorithms interviews. The question requires applying array and interval-processing concepts at an implementation level rather than purely conceptual understanding.
Each participant has a list of busy half-open intervals `[start, end)` for a single day on an integer timeline. Given `day_start` and `day_end` (the bookable working window `[day_start, day_end)`), `schedules` (a list of participants, each a list of busy intervals in any order that may overlap or touch), and a positive integer `duration`, return the list of maximal time windows, clipped to `[day_start, day_end)`, during which every participant is simultaneously free and whose length is at least `duration`. Return each window as a `[start, end)` pair, sorted ascending by `start`; return an empty list if none exist.
Notes: a participant with no busy intervals is free for the entire window; busy intervals may extend outside `[day_start, day_end)` and only the portion inside matters; free windows on opposite sides of a busy interval are never merged; each free window must be extended maximally before clipping and applying the duration filter.
Constraints
- day_start < day_end; both are integers on a shared timeline.
- duration is a positive integer.
- Each busy interval satisfies start < end; intervals per participant may be unsorted, overlapping, or touching.
- Busy intervals may extend beyond [day_start, day_end); only the clipped portion matters.
- A participant may have zero busy intervals (free for the whole window).
Examples
Input: (540, 1080, [[[600, 660], [780, 840]], [[540, 600], [900, 960]]], 60)
Expected Output: [[660, 780], [840, 900], [960, 1080]]
Explanation: Union of busy times merges to [540,660), [780,840), [900,960). The free gaps in [540,1080) are [660,780) (120), [840,900) (60), [960,1080) (120); all meet duration 60.
Input: (540, 1080, [[[600, 660], [780, 840]], [[540, 600], [900, 960]]], 90)
Expected Output: [[660, 780], [960, 1080]]
Explanation: Same free gaps as above, but with duration 90 the 60-minute window [840,900) is filtered out.
Input: (0, 100, [[]], 10)
Expected Output: [[0, 100]]
Explanation: The single participant has no busy intervals, so the entire working window [0,100) is free.
Input: (0, 60, [[[0, 60]]], 10)
Expected Output: []
Explanation: The only participant is busy for the whole window, leaving no free time.
Input: (0, 100, [[[-50, 30], [20, 40]], [[80, 200]]], 5)
Expected Output: [[40, 80]]
Explanation: After clipping to [0,100) and merging, busy = [0,40) and [80,100), leaving the single free window [40,80).
Input: (0, 30, [[], []], 100)
Expected Output: []
Explanation: Both participants are fully free so the whole [0,30) window is free, but its length 30 is below the required duration 100.
Input: (0, 200, [[[50, 60]], [[100, 110]], [[10, 20]]], 30)
Expected Output: [[20, 50], [60, 100], [110, 200]]
Explanation: Combined busy = [10,20), [50,60), [100,110); the gaps of length >= 30 are [20,50), [60,100), and [110,200).
Hints
- The set of times when everyone is free is exactly the complement of the union of all participants' busy intervals within the working window — so pool every busy interval together regardless of which participant it belongs to.
- Clip each busy interval to [day_start, day_end) up front and drop empties, then sort all busy intervals and merge overlapping OR touching ones (merge when the next start <= current end).
- Sweep the merged busy intervals to emit the gaps between them (and the leading/trailing gaps against day_start/day_end), then keep only gaps whose length is >= duration.