The coding question
You're given a list of reservations, each with a check-in and check-out date. Return the largest number of reservations that are active at the same time.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| If one guest checks out on the day another checks in, do they overlap? | No. A stay covers nights from check-in up to but not including check-out, so the check-out day is free. |
| What do the dates look like? | Strings like '2024-06-01'. They sort correctly as text, so we don't need to parse them. |
| Is check-out always after check-in? | Yes, every stay is at least one night. |
| How many reservations? | Up to about 100,000, so we want better than comparing every pair. |
A couple of examples
| Input | Output |
|---|---|
| (06-01 to 06-04), (06-02 to 06-05), (06-03 to 06-06) | 3, all three are in on the night of June 3 |
| (06-01 to 06-03), (06-03 to 06-05) | 1, the first guest leaves the day the second arrives |
| (06-01 to 06-10), (06-02 to 06-03), (06-04 to 06-05), (06-04 to 06-08) | 3, on June 4 |
Start with brute force
For every night between the earliest check-in and the latest check-out, count how many reservations cover it, and keep the biggest count. Or, for each reservation's check-in, count how many others are active then.
Cost: O(n × d) for the night-by-night version, where d is the number of days covered, or O(n²) for the pair version. That's billions of steps for 100,000 reservations.
A better way
The count only changes on check-in and check-out days. So turn each reservation into two events: +1 on check-in and -1 on check-out. Sort the events by date and walk through them with a running count. The biggest the count ever gets is the answer.
The edge case is the same day. Since a check-out frees the room before a check-in that day, the -1 has to come before the +1 when dates tie. If we store events as (date, change), sorting naturally puts -1 before +1. Nice.
Another way that's good to mention: sort by check-in and keep a heap of check-out dates for guests still staying. Before adding someone, pop everyone who's checked out by then. The heap's biggest size is the answer.
- Make a list of events: (check-in, +1) and (check-out, -1) for each reservation.
- Sort the events. Ties on date put -1 first.
- Walk through them, adding each change to a running count.
- Track the largest count you see and return it.
The code
def peak_reservations(reservations):
# Each reservation is (check_in, check_out) as "YYYY-MM-DD" strings.
# A guest leaves on the check-out day, so check-out frees the room
# before anyone checks in that same day.
events = []
for check_in, check_out in reservations:
events.append((check_in, 1))
events.append((check_out, -1))
# Sorting puts -1 before +1 on the same date.
events.sort()
active = 0
peak = 0
for _, change in events:
active += change
peak = max(peak, active)
return peak| Cost | Why | |
|---|---|---|
| Time | O(n log n) | Sorting 2n events. The walk after is O(n) |
| Space | O(n) | The list of events |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- No reservations: there are no events, so it returns 0.
- One guest checks out the same day another checks in: the -1 sorts first, so the count never hits 2.
- Several identical reservations: they all count, so three copies of the same stay gives 3.
- Stays across a year boundary, like 2024-12-30 to 2025-01-02: the date strings still sort correctly.
Common mistakes
- Sorting +1 before -1 on ties, which counts a check-out and check-in on the same day as overlapping.
- Counting the check-out night as part of the stay.
- Only checking each reservation against its neighbor after sorting, which misses long stays that cover many others.
- Comparing dates in a format that doesn't sort as text, like '6/1/2024'.
Follow-up questions
What if you also need to say when the peak happened?
Remember the date of the event that set a new peak. Since -1s come first, that's the check-in day the count reached its highest.
What if reservations keep coming in and you need the peak per room type?
Group events by room type in a hash map and run the same sweep per group. For live updates, keep a count per night per room type instead and update the nights each new booking covers.
What if a hotel has 5 rooms. Is any night overbooked?
Same sweep, but stop and return the date as soon as the count goes over 5.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Ask about same-day check-out and the input format |
| 5–10 | Brute force: count each night |
| 10–20 | Turn reservations into +1 and -1 events, and sort out ties |
| 20–35 | Write the code |
| 35–40 | Test with the examples and the same-day edge case |
| 40–45 | Follow-up questions |
Key concepts used here
- Heaps and priority queuesAlways have the smallest or largest item ready.
- Hash maps and sliding windowsSwap nested loops for a single pass.
- IntervalsMerge, insert and schedule ranges without tripping over the edges.
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Booking.com.