SeniorDesignRareNot answered yet
Given each guest's check-in and check-out dates (check-in strictly before check-out, so every guest stays at least one night), design an algorithm that finds the maximum number of guests staying in the hotel at the same time. On any shared day a departing guest leaves before a new guest arrives. Describe your data structures, the time complexity, and how you handle the tie-break when intervals touch at one point.
Use a sweep line: split each stay into a +1 check-in and a −1 check-out event, sort by time, and sweep keeping a running count whose maximum is the answer. At a shared time process check-outs before check-ins. O(N log N) for the sort.
- ✗Getting the tie-break wrong at a shared day, counting a departure and arrival as simultaneous
- ✗Using a day-indexed array that blows up when dates span a huge range
- ✗Forgetting that check-out frees a slot, so the −1 must be applied at the right moment
- →How would you also report which day (or days) had the peak occupancy?
- →What changes if you must support streaming stays added one at a time?
Contents
Scenario
A hotel wants the maximum simultaneous occupancy from each guest's check-in/check-out dates.
Discussion
This is a classic sweep line (like "meeting rooms II"):
- Each stay
[in, out)yields two events:(in, +1)and(out, −1). - Sort events by time; on a tie process
−1first (departing before arriving). - Sweep left to right, tracking a running count
curand its maximumpeak.
Complexity: O(N log N) for the sort, O(N) sweep, O(N) memory.
Contents
