Hotel Booking System
Design a hotel booking system. Dates are integers and every range is half-open [start, end) with 0 <= start < end, so a checkout at 14 and a check-in at 14 do not collide. Implement HotelBookingSystem(roomIds):
checkAvailability(start, end)— the ids of rooms with no booking overlapping the range, sorted ascending;[]for an invalid range.bookRoom(customer, roomId, start, end)— book and return a new id"B1","B2", … (numbered by successful bookings), ornullwhen the room is unknown, the range is invalid, or it overlaps an existing booking for that room.cancel(bookingId)— free the slot and returntrue;falsefor an unknown or already-cancelled id.
hotel = HotelBookingSystem(["101", "102"])
hotel.bookRoom("ann", "101", 1, 3) -> "B1"
hotel.checkAvailability(2, 4) -> ["102"]
hotel.bookRoom("bob", "101", 2, 4) -> null // overlaps B1
hotel.bookRoom("bob", "101", 3, 5) -> "B2" // half-open: 3 is free
hotel.cancel("B1") -> trueHints
Hint 1
Keep each room's bookings sorted by start. Two half-open ranges overlap when a.start < b.end and b.start < a.end; in a sorted, non-overlapping list only the neighbours of the insertion point can clash, so a binary search plus two checks decides a booking.
Hint 2
Check-then-book must be one atomic step per room: between a passing availability check and the insert, another caller can book the same slot. One lock per room is the smallest granularity that keeps the invariant; a global lock serialises the whole hotel.