Peak Concurrent Bookings

Problem

You are building a room booking system for a conference center. Given a list of bookings, each with a start and end timestamp (in minutes), determine the maximum number of bookings that are active at the same time (peak concurrent occupancy).

A booking is considered active during the interval [start, end) — i.e., a booking that ends at time t does not overlap with a booking that starts at time t.

Input Format

• bookings: a list of pairs [start, end] where each pair represents a booking interval.
• start and end are integers representing timestamps in minutes.

Output Format

• Return a single integer representing the peak number of concurrent bookings.

Examples

Example 1:

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

At time t=3, all three bookings [1,4], [2,6], and [3,5] are active simultaneously.

Example 2:

Input: bookings = [[1, 3], [3, 6], [6, 9]]
Output: 1

No two bookings overlap (each ends exactly when the next begins), so the max concurrency is 1.

Example 3:

Input: bookings = [[1, 10], [2, 4], [5, 7], [8, 9]]
Output: 2

The booking [1,10] overlaps with each of the other three, but the others don't overlap each other, so the max is 2.

Approach Hints

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

Optimal — Sweep Line / Event Counting (O(n log n)):

1. For each booking, create two events: a +1 event at the start time and a −1 event at the end time.
2. Sort all events by time. When times are equal, process end events (−1) before start events (+1) to respect the half-open interval semantics.
3. Sweep through events, maintaining a running count. Track the maximum count seen.

This approach leverages the insight that concurrency only changes at booking boundaries, allowing you to efficiently find the peak without checking every point in time.