Gate assignment board
MediumOnline Assessment
Run the gate board of a small airport: decide where each arriving aircraft parks and when it gets to dock.
gates[g] is the size (1 to 3) of gate g, numbered from 0. Each flight [arrival, dwell, size] reaches the airport at minute arrival, needs a gate with gate size >= size, and once docked stays dwell minutes. After it leaves, the gate cannot be used for buffer more minutes (cleaning). All gates are ready at minute 0.
At every minute t, first all flights with arrival <= t that are not yet docked join the waiting list, in arrival order (flights with the same arrival keep the order given). Then, going through the waiting list from the front, each flight docks at minute t if a gate is ready (a gate is ready from the minute its last flight left plus buffer). Among the ready gates that are big enough it takes the smallest one, and the lowest-numbered of those if several have the same size. A flight that finds no suitable gate stays on the list, and flights behind it are still considered, so a small flight can be served ahead of a larger one that cannot fit anywhere.
Input: gates, buffer, and flights as described.
Output: a list with one [gate, dockMinute] pair per flight, in the order of the input.
Example 1
- Input:
- [[1,2,3],10,[[0,30,1],[5,20,1],[8,40,3],[15,10,2]]]
- Output:
- [[0,0],[1,5],[2,8],[1,35]]
- Explanation
- Flight 0 takes the smallest gate that fits, gate 0 (size 1). Flight 1 arrives while gate 0 is busy, so it takes gate 1, the next smallest. Flight 2 needs size 3 and takes gate 2. Flight 3 (size 2) arrives at 15 and finds no free gate it fits: gate 1 is occupied until 5 + 20 + 10 = 35, so it docks there at 35.
Example 2
- Input:
- [[1,3],10,[[0,50,3],[1,20,3],[2,10,1],[3,5,1]]]
- Output:
- [[1,0],[1,60],[0,2],[0,22]]
- Explanation
- Flight 0 takes gate 1 (the only size 3 gate) and keeps it until 60. Flight 1 also needs size 3 and must wait. Flight 2 (size 1) takes gate 0 at once. Flight 3 (size 1) finds both gates busy and waits. Gate 0 is ready again at 2 + 10 + 10 = 22; flight 1 (size 3) is ahead of flight 3 in the list but cannot use gate 0, so flight 3 docks there at 22. Flight 1 docks at gate 1 at 0 + 50 + 10 = 60.
Example 3
- Input:
- [[1,2],10,[[0,10,1],[1,10,1],[5,10,2],[20,5,1]]]
- Output:
- [[0,0],[1,1],[1,21],[0,20]]
- Explanation
- Flight 1 (size 1) takes the big gate 1 because gate 0 is busy. Flight 2 (size 2) arrives at 5 and has to wait until gate 1 is ready at 21. Gate 0 becomes ready at 20, exactly when flight 3 arrives; flight 2 cannot use gate 0 (too small), so flight 3 docks there at 20.
Constraints
1 <= gates.length <= 12,1 <= gates[g] <= 30 <= buffer <= 600 <= flights.length <= 200- Each flight is
[arrival, dwell, size]with0 <= arrival <= 10,000,1 <= dwell <= 300,1 <= size <= 3, andsizenever exceeds the largest gate - Flights are listed in non-decreasing order of
arrival