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 ```python 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** ```text 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** ```text 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** ```text 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)`.