Find earliest common meeting slot
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
Given the calendars of `N` attendees, find the **earliest** time window of length at least `d` minutes during which **all** attendees are simultaneously free.
Each attendee's calendar is a sorted list of non-overlapping, half-open **busy** intervals `[start, end)` (times in minutes since the epoch). Each attendee also has a daily **working-hours window**; a valid slot must fall inside every attendee's working hours. Return the earliest start time `t` such that every attendee is free for `d` consecutive minutes starting at `t` (equivalently, return the `[start, end)` slot). If no such slot exists, return `-1`.
**Example.**
- Attendee A busy: `[[60, 120), [180, 240)]`, working hours `[0, 480)`
- Attendee B busy: `[[0, 90), [150, 200)]`, working hours `[30, 480)`
- Required duration `d = 30`
The first window of length ≥ 30 free for both inside both working windows starts at `t = 120` (A and B are both free on `[120, 150)`), so return `120`.
Discuss the algorithm and its time/space complexity, then address the follow-ups below.
##### Follow-ups
1. **Multiple participants.** Generalize cleanly from 2 attendees to `N`. What changes in the algorithm and the complexity?
2. **Time zones.** Attendees may be in different time zones and have different working hours per local day. How do you normalize times and handle DST so the answer is correct?
3. **Fragmented / very large inputs.** Schedules can be highly fragmented with up to ~`1e6` total intervals. How do you keep the solution efficient, and how does fragmentation affect cost?
4. **API design for "now".** Redesign the function so it only considers free slots strictly after the current time **without** taking `now` as a parameter. Discuss injecting a monotonic clock, testability, and determinism.
5. **Concurrency.** Calendars may be updated concurrently while `find-meeting` calls execute. Describe how you keep reads consistent and writes safe (locks vs. copy-on-write vs. versioned snapshots), the data structures involved, and how you avoid starvation.
Quick Answer: An Uber Software Engineer onsite coding question: given N attendees' busy calendars as sorted half-open intervals plus per-attendee working hours, find the earliest time window of length d in which everyone is simultaneously free, or return -1. It covers the merge-busy/scan-gaps algorithm and complexity, then follow-ups on scaling to N participants, time zones and DST, very large fragmented inputs, clock-injection API design, and concurrency control for live calendar updates.
Given the calendars of `N` attendees, find the **earliest** start time `t` of a window of length at least `d` minutes during which **all** attendees are simultaneously free.
Each attendee's calendar is a sorted list of non-overlapping, half-open **busy** intervals `[start, end)` (times in minutes since the epoch). Each attendee also has a daily **working-hours window** `[ws, we)`; a valid slot must fall inside **every** attendee's working hours. Return the earliest start time `t` such that every attendee is free for `d` consecutive minutes starting at `t` (the slot is `[t, t + d)`). If no such slot exists, return `-1`.
**Function signature:** `solution(calendars, working_hours, d)` where `calendars[i]` is the sorted list of `[start, end)` busy intervals for attendee `i`, `working_hours[i]` is `[ws, we)` for attendee `i`, and `d` is the required duration.
**Example.**
- Attendee A busy: `[[60, 120], [180, 240]]`, working hours `[0, 480]`
- Attendee B busy: `[[0, 90], [150, 200]]`, working hours `[30, 480]`
- `d = 30`
Both attendees are free on `[120, 150)`, which has length 30 inside both working windows, so the earliest valid start is `t = 120`.
**Approach:** The clean reframe is to intersect all working-hour windows into a common window `W = [max(ws), min(we))`, merge every attendee's *busy* intervals (clipped to `W`) into one timeline of "someone-is-busy" blocks, then scan the gaps between consecutive busy blocks for the first gap of length `>= d`. Respect the half-open convention: intervals `[a, b)` and `[b, c)` are adjacent (not overlapping) and leave no free time at `b`.
**Constraints note:** Times can be any integers (including negative epoch-minute values). An empty calendar means that attendee is free for the whole window. If the common working window is shorter than `d`, return `-1`.
*(Discussion follow-ups in the original prompt — N participants, time zones/DST, ~1e6 fragmented intervals, injecting a clock for "now", and concurrent updates — are conceptual; the console verifies the core algorithm.)*
Constraints
- 1 <= N (number of attendees); each attendee has a working-hours window [ws, we) with ws < we
- Each attendee's busy list is sorted, non-overlapping, and uses half-open [start, end) intervals
- Total busy intervals M can be large (up to ~1e6 in the fragmented follow-up)
- Times are integers in minutes since the epoch and may be negative
- An empty calendar means that attendee is free for the entire window
- Return -1 if no qualifying slot exists (including when the common working window is shorter than d)
Examples
Input: ([[[60, 120], [180, 240]], [[0, 90], [150, 200]]], [[0, 480], [30, 480]], 30)
Expected Output: 120
Explanation: Common window [30,480). Merged busy = [0..120) (A's [60,120) clipped, B's [0,90)) then [150,240). Gap [120,150) has length 30 >= d, so earliest start is 120.
Input: ([[[0, 480]]], [[0, 480]], 30)
Expected Output: -1
Explanation: The single attendee is busy for the entire working window [0,480), leaving no free gap of length 30.
Hints
- Intersect all working-hour windows first: the feasible region is W = [max(ws), min(we)). If W is empty or shorter than d, return -1 immediately.
- Don't intersect free intervals pairwise across attendees — instead merge all attendees' busy intervals into one sorted timeline, then look at the gaps between consecutive busy blocks.
- Walk left to right tracking prev_end (start it at W.start). The first busy block whose start minus prev_end is >= d gives the answer prev_end. Remember to check the tail gap [last_end, W.end) too.
- Half-open matters: busy [a, b) followed by busy [b, c) are adjacent, not overlapping, and leave no free time at b — so treat touching blocks as merged and never report a zero-length slot.