Charging Bay Queue
Medium · heap
A charging station has bays charging bays, numbered from 0. Electric cars arrive one at a time. You are given two lists: arrivals[i] is the time car i arrives, and durations[i] is how long it needs to charge. The arrival times are all different and are given in increasing order.
When a car arrives it takes the free bay with the lowest number. A bay is free if its last car finished at or before this moment. If every bay is busy, the car waits and takes the bay that becomes free soonest (the lowest-numbered one if several free up at the same time). It then starts charging at that moment, so it finishes durations[i] after the start.
Return the number of the bay that charged the most cars. If several bays share the highest count, return the lowest-numbered one.
Examples
Example 1
Input: bays = 2, arrivals = [1, 2, 3, 4], durations = [10, 1, 1, 1]
Output: 1
Car 0 takes bay 0 until time 11. Car 1 takes bay 1 and leaves at time 3, exactly when car 2 arrives, so car 2 uses bay 1 as well, and so does car 3.
Example 2
Input: bays = 2, arrivals = [1, 2, 3], durations = [6, 6, 1]
Output: 0
Car 2 finds both bays busy. Bay 0 frees at time 7 and bay 1 at time 8, so it waits for bay 0. Bay 0 charged two cars and bay 1 charged one.
Example 3
Input: bays = 3, arrivals = [5, 6], durations = [2, 2]
Output: 0
Each car takes a free bay, bay 0 and bay 1, so both bays charged one car. The tie goes to the lower number.
Constraints
- 1 <= bays <= 10^5
- 1 <= len(arrivals) <= 10^5
- len(durations) == len(arrivals)
- 1 <= arrivals[i] <= 10^8, and arrivals is strictly increasing
- 1 <= durations[i] <= 10^4