""" p50 — Employee Free Time (LeetCode 759, HARD). Input: List[List[Interval]] — each employee's busy times, sorted & disjoint. Output: List[Interval] of free times common to all, clipped to [first_event, last_event]. Three implementations: employee_free_time_flatten — flatten + sort + merge + invert. O(N log N). employee_free_time_heap — K-way merge with min-heap + max_end invariant. O(N log K). employee_free_time_brute — discretize minute-by-minute (oracle, tiny only). Free time = gaps BETWEEN merged busy intervals. Excludes time before first or after last. """ from __future__ import annotations import heapq import random from typing import List class Interval: """Minimal stand-in for LC's Interval type.""" __slots__ = ("start", "end") def __init__(self, start: int = 0, end: int = 0): self.start = start self.end = end def __eq__(self, other): return isinstance(other, Interval) and self.start == other.start and self.end == other.end def __repr__(self): return f"[{self.start},{self.end}]" def _as_tuples(intervals: List[Interval]) -> List[tuple]: return [(i.start, i.end) for i in intervals] # -------------------------------------------------------------------------------------- # Approach A: flatten + sort + merge + invert. O(N log N). # -------------------------------------------------------------------------------------- def employee_free_time_flatten(schedule: List[List[Interval]]) -> List[Interval]: flat = [(iv.start, iv.end) for emp in schedule for iv in emp] if not flat: return [] flat.sort(key=lambda x: x[0]) # Merge merged: List[List[int]] = [list(flat[0])] for s, e in flat[1:]: if s <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], e) else: merged.append([s, e]) # Invert: gaps between consecutive merged intervals out: List[Interval] = [] for i in range(1, len(merged)): if merged[i - 1][1] < merged[i][0]: out.append(Interval(merged[i - 1][1], merged[i][0])) return out # -------------------------------------------------------------------------------------- # Approach B: K-way merge with heap. O(N log K). # Heap entries: (start, employee_idx, interval_idx_within_employee) # INVARIANT: max_end = max end-time over all intervals popped so far. # Emit free slot whenever next.start > max_end. # -------------------------------------------------------------------------------------- def employee_free_time_heap(schedule: List[List[Interval]]) -> List[Interval]: heap: List[tuple] = [] for ei, emp in enumerate(schedule): if emp: heap.append((emp[0].start, ei, 0)) if not heap: return [] heapq.heapify(heap) out: List[Interval] = [] # Bootstrap with first popped interval start, ei, ii = heapq.heappop(heap) max_end = schedule[ei][ii].end if ii + 1 < len(schedule[ei]): nxt = schedule[ei][ii + 1] heapq.heappush(heap, (nxt.start, ei, ii + 1)) while heap: start, ei, ii = heapq.heappop(heap) cur = schedule[ei][ii] if start > max_end: out.append(Interval(max_end, start)) max_end = max(max_end, cur.end) if ii + 1 < len(schedule[ei]): nxt = schedule[ei][ii + 1] heapq.heappush(heap, (nxt.start, ei, ii + 1)) return out # -------------------------------------------------------------------------------------- # Brute oracle: discretize minute by minute over [lo, hi]; collect runs where active == 0. # (Skip the prefix before any interval and suffix after.) # -------------------------------------------------------------------------------------- def employee_free_time_brute(schedule: List[List[Interval]]) -> List[Interval]: flat = [(iv.start, iv.end) for emp in schedule for iv in emp] if not flat: return [] lo = min(s for s, _ in flat) hi = max(e for _, e in flat) out: List[Interval] = [] gap_start = None for t in range(lo, hi): busy = any(s <= t < e for s, e in flat) if not busy: if gap_start is None: gap_start = t else: if gap_start is not None: out.append(Interval(gap_start, t)) gap_start = None # No suffix gap by construction (loop stops at hi - 1; t = hi - 1 is inside last interval). return out def _to_tuples(intervals: List[Interval]) -> List[tuple]: return [(i.start, i.end) for i in intervals] # -------------------------------------------------------------------------------------- # Tests # -------------------------------------------------------------------------------------- def edge_cases() -> None: # LC canonical 1 sched = [ [Interval(1, 2), Interval(5, 6)], [Interval(1, 3)], [Interval(4, 10)], ] assert _to_tuples(employee_free_time_flatten(sched)) == [(3, 4)] assert _to_tuples(employee_free_time_heap(sched)) == [(3, 4)] # LC canonical 2 sched = [ [Interval(1, 3), Interval(6, 7)], [Interval(2, 4)], [Interval(2, 5), Interval(9, 12)], ] assert _to_tuples(employee_free_time_flatten(sched)) == [(5, 6), (7, 9)] assert _to_tuples(employee_free_time_heap(sched)) == [(5, 6), (7, 9)] # No gaps (everyone continuously busy) sched = [[Interval(1, 10)]] assert employee_free_time_flatten(sched) == [] assert employee_free_time_heap(sched) == [] # Empty schedule assert employee_free_time_flatten([]) == [] assert employee_free_time_heap([]) == [] # Some employees with no intervals sched = [[], [Interval(1, 3), Interval(5, 7)], []] assert _to_tuples(employee_free_time_flatten(sched)) == [(3, 5)] assert _to_tuples(employee_free_time_heap(sched)) == [(3, 5)] print("edge_cases: PASS") def stress_test() -> None: rng = random.Random(42) for trial in range(200): K = rng.randint(1, 5) sched: List[List[Interval]] = [] for _ in range(K): n = rng.randint(0, 4) cur = rng.randint(0, 3) emp: List[Interval] = [] for _ in range(n): cur += rng.randint(1, 3) length = rng.randint(1, 4) emp.append(Interval(cur, cur + length)) cur += length sched.append(emp) a = _to_tuples(employee_free_time_flatten(sched)) b = _to_tuples(employee_free_time_heap(sched)) c = _to_tuples(employee_free_time_brute(sched)) assert a == b == c, f"trial {trial}: flat={a} heap={b} brute={c}" print("stress_test: 200 random trials — flatten, heap, brute all agree.") if __name__ == "__main__": edge_cases() stress_test() print("ALL TESTS PASSED")