Find earliest common meeting slot

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.

Find earliest common meeting slot

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)

Hints

1. 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.
2. 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.
3. 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.
4. 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.

Solution

Rubric: the strong candidate reframes the problem as merge-busy-then-scan-gaps (not pairwise free-interval intersection), respects the half-open [start,end) convention, intersects all working-hour windows, and returns -1 when infeasible. They give a clean k-way merge over the already-sorted per-attendee lists at O(M log N) time / O(N) space (or the simpler O(M log M) sort-then-merge), where M is total intervals. Generalizing 2→N is free in this framing. For time zones they compute in absolute (UTC/Instant) time and resolve local working hours + DST via the tz database per-instant. For 1e6 fragmented intervals they note cost scales with M, prefer streaming merge, and pre-clip to the working window and [now, horizon). For the API, they inject a Clock dependency (no now parameter, but swappable/fake-able) for determinism and testability. For concurrency they compare coarse/RW locks vs copy-on-write vs versioned MVCC snapshots, pin an immutable snapshot for consistent lock-free reads, use persistent interval trees, and keep critical sections short to avoid starvation.

This is a classic interval-merging / k-way-merge problem. The key reframe: instead of intersecting free intervals (error-prone), merge all attendees' busy intervals into one timeline of "someone is busy" intervals, then scan the gaps between consecutive busy blocks (clipped to the common working window) for the first gap of length ≥ d.

Core algorithm (the right approach)

1. Common working window. The slot must be inside every attendee's working hours, so the feasible region is the intersection of all working windows: W = [max(all start), min(all end)). If W is empty, return -1.
2. Merge all busy intervals. Collect every attendee's busy intervals, clip them to W, sort by start, and merge overlapping/adjacent ones into a single list of disjoint "busy-for-someone" intervals. (Because each attendee's list is already sorted and non-overlapping, you can do a k-way merge with a heap instead of a full sort — see complexity below.)
3. Scan the gaps. Walk the merged busy list left to right, tracking the end of the previous busy block (initialized to W.start). The free gap before the next busy block is [prev_end, next_start). The first gap with next_start - prev_end >= d yields the answer: return prev_end (slot [prev_end, prev_end + d)). After the last busy block, also check the tail gap [last_end, W.end).
4. If no gap qualifies, return -1.

Note the half-open [start, end) convention matters: an interval ending at t and another starting at t are adjacent, not overlapping, and leave no free time at t. Treat touching busy blocks as merged.

Reference implementation (Python)

import heapq

def earliest_common_slot(calendars, working_hours, d):
    # calendars: list[list[(start, end)]], each sorted, non-overlapping, half-open
    # working_hours: list[(start, end)] per attendee
    # returns earliest start t, or -1
    if not calendars:
        return -1
    W_start = max(w[0] for w in working_hours)
    W_end   = min(w[1] for w in working_hours)
    if W_end - W_start < d:
        return -1

    # k-way merge of already-sorted busy lists via a heap of (start, end, list_idx, pos)
    heap = []
    for i, cal in enumerate(calendars):
        if cal:
            s, e = cal[0]
            heapq.heappush(heap, (s, e, i, 0))

    prev_end = W_start
    while heap:
        s, e, i, pos = heapq.heappop(heap)
        # advance this list
        if pos + 1 < len(calendars[i]):
            ns, ne = calendars[i][pos + 1]
            heapq.heappush(heap, (ns, ne, i, pos + 1))

        # clip the busy interval to the common working window
        s = max(s, W_start)
        e = min(e, W_end)
        if s >= e:
            continue  # entirely outside the working window
        if s - prev_end >= d:
            return prev_end          # found a gap before this busy block
        prev_end = max(prev_end, e)  # extend the "busy-until" frontier
        if prev_end >= W_end:
            return -1

    # tail gap after the last busy block
    if W_end - prev_end >= d:
        return prev_end
    return -1

Complexity

Let M be the total number of busy intervals across all N attendees.

• k-way merge with a heap: O(M log N) time, O(N) extra space for the heap (we never materialize all M intervals at once).
• Simpler sort-then-merge variant: O(M log M) time, O(M) space — fine and often what's expected, but the heap version exploits the per-attendee sortedness and is the better answer for very large, fragmented inputs.
• We make a single left-to-right pass and return on the first qualifying gap, so we often stop early.

Follow-up 1 — Multiple participants (2 → N)

The busy-merge formulation generalizes for free: N is just the number of input lists fed into the k-way merge, and the common working window is an N-way intersection. Cost grows as O(M log N), dominated by total interval count M rather than N itself. Avoid the naive approach of pairwise-intersecting free intervals across attendees — that blows up combinatorially and is harder to get right than merging busy intervals once.

Follow-up 2 — Time zones & DST

• Store and compute in a single absolute timeline (UTC epoch minutes/seconds, or Instant). All interval math (merge, gap scan) happens in this tz-agnostic space, so the core algorithm is unchanged.
• Working hours are local. Convert each attendee's local working window (e.g., 9:00–17:00 in America/New_York) to absolute instants for the specific calendar day using their IANA time zone, because the UTC offset depends on the date.
• DST correctness: never store fixed offsets; resolve offsets per-instant via the tz database. On DST-transition days a local day can be 23 or 25 hours, and a local wall-clock time can be skipped or repeated — rely on the library's local-to-instant rules and document the policy for the ambiguous/skipped hour. Convert the final answer back to each viewer's local time for display.
• Edge case: a meeting window can straddle a DST boundary; since the math is in absolute time, duration d stays correct, but localized display must re-derive the offset on each side.

Follow-up 3 — Fragmented & very large inputs (~1e6 intervals)

• Cost is driven by total intervals M, not by attendee count — fragmentation (many tiny busy blocks) raises M and thus the dominant term.
• The streaming k-way merge keeps memory at O(N) and avoids re-sorting already-sorted inputs; prefer it over sort-then-merge at this scale.
• Pre-clip to the common working window and to [now, horizon) as early as possible to drop irrelevant intervals before merging.
• For repeated queries over slowly-changing calendars, precompute each attendee's free intervals or a segment/interval index so a query touches only the relevant range; or bucket the timeline and skip fully-busy buckets. If you only need a slot within a bounded horizon, you can stop the scan at the horizon.

Follow-up 4 — API design: no now argument

Passing now in makes the function non-deterministic to callers and easy to misuse; removing it but reading the wall clock inside makes it untestable. The clean design is dependency injection of a clock:

from typing import Protocol

class Clock(Protocol):
    def now(self) -> int: ...  # monotonic-ish 'current minute' source

class SystemClock:
    def now(self) -> int: return real_time_source()

class MeetingFinder:
    def __init__(self, clock: Clock = SystemClock()):
        self._clock = clock
    def find(self, calendars, working_hours, d):
        now = self._clock.now()
        # lower-bound the search window at `now`: prev_end starts at max(W_start, now)
        ...

• The public method takes no now parameter, satisfying the requirement, yet the time source is explicit and swappable.
• Testability/determinism: inject a FakeClock returning a fixed instant so tests are reproducible; production uses SystemClock.
• Monotonic vs wall clock: for measuring elapsed time / timeouts prefer a monotonic source (immune to NTP steps and DST), but the meeting search compares against calendar (wall-clock) instants, so the clock should expose the current wall-clock instant in the same absolute timeline as the intervals. The key point graders want: time is an injected dependency, not an ambient global.
• Initialize the scan frontier at max(common_working_start, now) so only slots strictly after the current time are returned.

Follow-up 5 — Concurrent calendar updates

Reads (find-meeting) must see a consistent calendar even while writes (add/remove busy intervals) happen.

• Coarse lock: a single mutex serializes everything — simplest and correct, but a long read blocks writers and vice-versa; readers can starve writers (or writers starve readers) under contention. A reader–writer lock improves read concurrency but can still starve writers; use a fair/writer-preferring variant to bound starvation.
• Copy-on-write (preferred for read-heavy workloads): writers build a new immutable calendar version and atomically swap a pointer; readers grab the current immutable snapshot and run lock-free. No reader blocks a writer or vice-versa; the trade-off is per-write copy cost (mitigated with persistent/immutable interval trees that share structure) and brief extra memory for in-flight versions.
• Versioned / MVCC snapshots: keep multiple immutable versions keyed by a version number; a find-meeting call pins a snapshot version for its whole run, guaranteeing a consistent read without blocking concurrent writers (which append new versions). Reclaim old versions once no reader references them. This is the most scalable and the natural answer for "updates while queries run."
• Data structures: immutable/persistent interval trees or sorted interval lists per attendee support O(log n) inserts/queries and cheap structural sharing for COW/MVCC.
• Starvation avoidance: prefer lock-free snapshot reads (COW/MVCC) so readers never block writers; if using locks, choose a fair RW-lock and keep critical sections short (do the heavy merge/scan on a pinned snapshot outside the lock).

Common pitfalls

• Mishandling the half-open convention: touching intervals ([a,b) then [b,c)) leave no free time at b; don't report a zero-length slot.
• Intersecting free intervals pairwise across attendees instead of merging busy intervals once — slower and bug-prone.
• Forgetting the working-hours intersection, or applying it per attendee inconsistently.
• Storing local times or fixed UTC offsets instead of absolute instants — breaks across time zones and DST.
• Reading the wall clock as an ambient global (untestable) or passing now in (misusable) instead of injecting a clock.
• Holding a lock across the full merge/scan, serializing all queries; pin an immutable snapshot and compute outside the lock.