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 => []
Hints
Hint 1
Turn each reservation into two events: +ppl at start, −ppl at end. Occupancy only changes at events, so it is constant on each segment between consecutive event times.
Hint 2
Walk the timeline once: open a free interval when capacity − occupied >= n, close it when that stops holding, and merge adjacent qualifying segments.
Hint 3
Half-open reservations mean a −ppl and a +ppl at the same instant must net before you judge that instant — process both before emitting.