Opening hours run from open_time to close_time, and the dining room seats capacity guests. The booking system already holds some reservations, each a triple [start, end, seats]: the party occupies seats seats during the half-open interval [start, end). The list is sorted by start (ties in any order), and every reservation lies inside opening hours: open_time <= start < end <= close_time.
A walk-in party of party people wants to stay for at least duration minutes. Implement
free_intervals(open_time: int, close_time: int, capacity: int,
reservations: list[list[int]], party: int, duration: int) -> list[list[int]]
Return every maximal half-open interval [a, b) inside [open_time, close_time) during which, at every moment, the seats already reserved plus party stay <= capacity, keeping only those with b - a >= duration. List them sorted by start. "Maximal" means two returned intervals never touch: [0, 5) and [5, 9) must be merged into [0, 9).
Constraints: 0 <= open_time < close_time <= 10**9, 1 <= capacity, party, seats, 1 <= duration, up to 100,000 reservations. The reservations themselves may overbook the room (the answer simply has no interval there).
free_intervals(0, 100, 10, [[10, 40, 6], [20, 50, 3], [60, 70, 10]], 4, 5)
# [[0, 20], [40, 60], [70, 100]]
# 0-10: 0 seats taken 10-20: 6 taken (6 + 4 <= 10, fits) 20-40: 9 taken (doesn't fit)
# 40-50: 3 taken 50-60: 0 taken 60-70: 10 taken (doesn't fit)
# 70-100: 0 taken
free_intervals(0, 100, 10, [[10, 40, 6], [20, 50, 3], [60, 70, 10]], 4, 25)
# [[70, 100]] (the other two are shorter than 25 minutes)
free_intervals(0, 100, 5, [], 6, 1)
# [] (the party is bigger than the restaurant)
A reservation list can be long and times go up to 10**9, so don't walk minute by minute, and don't compare every reservation with every other one.
Show hint
Sweep line. Turn each reservation into +seats at start and -seats at end, visit the distinct times in order (plus open_time and close_time), and between consecutive times you know exactly how many seats are taken. Extend the current interval while the party fits, close it when it doesn't, and filter by duration at the end.