Peak number of bikes needed to cover all pre-booked rental intervals

A bike rental service receives every booking ahead of time. Each booking reserves one bike from a start time until an end time. Write a function that returns the peak number of bikes needed at any point in time: the number of bookings in use at the busiest moment, which is also the smallest fleet that can serve every booking.

Function Signature

def peak_bike_demand(bookings: list[list[int]]) -> int:

Rules

• bookings[i] = [start, end] reserves one bike for the half-open interval [start, end): the bike is in use at every time t with start <= t < end.
• A bike returned at time t can be rented out again at time t, so a booking that ends at t and a booking that starts at t never need two bikes at once.
• Bikes are interchangeable. Identical bookings are separate bookings, and each needs its own bike.
• Return the maximum, over all times t, of the number of bookings in use at t. Return 0 when there are no bookings.

Constraints

• 0 <= len(bookings) <= 10^5
• 0 <= start < end <= 10^9 for every booking
• Times are integers (for example, minutes from the start of the booking period), so every value fits in a 32-bit signed integer.
• bookings is in no particular order.

Examples

Example 1

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

At time 3, the bookings [1, 4), [2, 5) and [3, 6) are all in use. No moment has more.

Example 2

Input: bookings = [[1, 3], [3, 5], [5, 7]]
Output: 1

Each booking starts exactly when the previous one ends, so one bike can serve all three in turn.

Example 3

Input: bookings = [[5, 10], [5, 10], [9, 12], [10, 11]]
Output: 3

At time 9, both copies of [5, 10) and the booking [9, 12) are in use. At time 10, the two copies have ended, leaving [9, 12) and [10, 11).