Peak Concurrent Bookings

Problem

You are building a room reservation system for a co-working space. Given a list of bookings where each booking has a start and end timestamp (in minutes), determine the peak concurrent occupancy — the maximum number of bookings that overlap at any single point in time.

A booking [s, e] occupies the room during the interval [s, e) (inclusive start, exclusive end). Two bookings overlap if one starts before the other ends.

Input Format

• A 2D integer array bookings where bookings[i] = [start_i, end_i]
• Each booking represents a time interval [start_i, end_i)

Output Format

• Return a single integer representing the maximum number of bookings active at the same time.

Examples

Example 1

Input: bookings = [[1, 4], [2, 6], [5, 8]]
Output: 2
Explanation:

• At time 1: booking 0 starts → 1 active
• At time 2: booking 1 starts → 2 active
• At time 4: booking 0 ends → 1 active
• At time 5: booking 2 starts → 2 active
• At time 6: booking 1 ends → 1 active
  Peak is 2.

Example 2

Input: bookings = [[1, 10], [2, 8], [3, 7], [4, 6]]
Output: 4
Explanation: All four bookings overlap at time 4. Peak is 4.

Example 3

Input: bookings = [[1, 3], [4, 6], [7, 9]]
Output: 1
Explanation: No two bookings overlap (they are back-to-back with exclusive ends). Peak is 1.

Approach Hints

Brute Force (O(n²)): For every booking, count how many other bookings overlap with it. Return the maximum count. This will be too slow for large inputs.

Efficient Approach — Event Sweep (O(n log n)):

1. Convert each booking [s, e] into two events: a +1 at time s (arrival) and a -1 at time e (departure).
2. Sort all events by time. If two events share the same time, process departures before arrivals to avoid overcounting (since end is exclusive).
3. Sweep through the sorted events, maintaining a running count. Track the maximum value seen.

This approach runs in O(n log n) time due to sorting, and O(n) space for the events array.