The Question

Minimum Hotel Rooms Required

Given two integer arrays arrivals and departures representing the check-in and check-out times of guests at a hotel, calculate the minimum number of rooms required to accommodate all guests. A room can be reused immediately if a guest checks out at the same time another guest checks in (e.g., a checkout at time 5 and a check-in at time 5 do not overlap). Constraints: - 1 <= arrivals.length == departures.length <= 10^5 - 0 <= arrivals[i] < departures[i] <= 10^9 - The input arrays are not necessarily sorted.

Java

Sweep Line

Two-pointer

Sorting

Questions & Insights

Clarifying Questions

Overlap Handling: If a guest checks out at 12:00 PM and another guest checks in at 12:00 PM, does this require two separate rooms or can the same room be reused? (Assumption: Reusable, so departure <= arrival is not an overlap).

Input Format: Are the inputs provided as a list of interval objects, a 2D array, or two separate arrays for arrivals and departures? (Assumption: Two separate integer arrays for simplicity).

Scale: What is the maximum number of bookings? (Assumption: Up to

10^5

, requiring an

O(N \log N)

solution).

Time Representation: Are the times given as integers (e.g., days) or timestamps? (Assumption: Integers representing time units).

Thinking Process

To find the minimum rooms, we need to find the maximum number of concurrent bookings at any single point in time.

A "Sweep Line" approach is ideal here: treat every check-in as a "+1 room" event and every check-out as a "-1 room" event.

Sort all arrival and departure times independently. We don't need to keep them paired because we only care about how many guests are physically in the hotel at any moment.

Iterate through the sorted arrivals. For each arrival, check if the earliest scheduled departure has already occurred. If it has, a room is freed up (increment the departure pointer). If not, we need a new room (increment the room count).

Implementation Breakdown

Problem Set

Functional Requirements:

Input: int[] arrivals, int[] departures.

Output: int representing the minimum rooms needed.

Constraints:

N \le 100,000

0 \le arrivals[i] < departures[i]

Memory limit: 256MB.

Time limit: 1s.

Approach

Algorithm: Sweep Line (Two-pointer approach on sorted arrays).

Data Structure: Primitive Arrays.

Complexity:

Time:

O(N \log N)

due to sorting.

Space:

O(1)

if we sort in place, or

O(N)

for copies of the input arrays.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: While sorting two separate arrays is

O(N \log N)

, we could use a TreeMap if times were discrete and sparse, but for dense inputs, the array-based two-pointer is faster due to cache locality.

Streaming/Iterative: If the bookings were arriving as a stream, we could use a Min-Heap (Priority Queue) to track departure times. For every new arrival, we peek at the heap; if the smallest departure time is

\le

current arrival, we poll (reuse room) and push the new departure.

Real-time Distributed Adaptation: In a distributed system like Booking.com, this data would be in a database (e.g., PostgreSQL). The query would involve an interval overlap check or using an exclusion constraint on a GiST index to ensure no double-booking at the DB level.