Restaurant Seating: Free Intervals

A restaurant is open from openT to closeT and has capacity seats. Existing reservations are (start, end, ppl) — half-open [start, end), and times may be fractional. Given a party size n, return all maximal time intervals [a, b] within opening hours during which the party could be seated: free seats >= n for the whole interval.

open 9, close 22, capacity 5
reservations = [(10,14,3), (11,13,2), (13.5,15,1), (16,20,2)]
n = 2  =>  [[9,11], [13,13.5], [14,22]]
n = 3  =>  [[9,10], [14,22]]
n = 6  =>  []

Follow-ups

• The party also needs a slot at least duration long — filter the intervals.
• Book the party into the first feasible slot (now state mutates) — what structure keeps this fast?
• Many queries with different n — precompute the occupancy step function once, answer each query in O(#segments).
• Peak occupancy / max party size at time t — the classic Meeting Rooms II questions.