Ferry Deck Loader
MediumOnline Assessment
Load vehicles onto a ferry's lanes, then work out who leaves where and how many vehicles have to be shuffled out of the way.
The ferry deck has parallel lanes numbered from 0; lanes[k] is the length of lane k in metres. Vehicles drive on through a ramp at the stern, so each lane behaves like a stack: the vehicle that boarded last is nearest the ramp and is the first one that can leave.
vehicles[i] = [length, dest] is the i-th vehicle to arrive at the origin port (index i, boarding in this order) and the stop number dest where it gets off. Vehicles in the same lane must be at least 1 metre apart, but the first vehicle in a lane needs no gap. So a lane holding vehicles of lengths a, b, c uses a + b + c + 2 metres, and a new vehicle of length x fits only if the used metres plus x (plus 1 if the lane is not empty) is at most the lane length.
Boarding. Each vehicle takes the lowest-numbered lane it fits in, even if a later lane would fit it more tightly. If no lane fits it, it is refused and stays on the quay; later vehicles still try to board.
Stops. The ferry then calls at stops 1, 2, 3, ... in order. At stop s, lanes are processed from lane 0 upward. In a lane, every vehicle with dest == s must leave. Vehicles are driven off from the ramp end, so any vehicle that boarded the lane after the deepest (earliest boarded) vehicle with dest == s and that is not itself getting off here has to drive off temporarily and drive back on afterwards, in the same order, which counts as one shuffle per such vehicle. Vehicles leaving at this stop leave in the order they are reached, nearest the ramp first. Stops where nobody leaves cost nothing.
Input: lanes and vehicles.
Output: a list [refused, order, shuffles]: the indices of the refused vehicles in increasing order, the indices of all other vehicles in the order they leave the ferry over the whole trip (stop by stop, lane by lane, ramp end first), and the total number of shuffles.
Example 1
- Input:
- [[10,6],[[4,1],[5,2],[3,1],[6,3],[2,2]]]
- Output:
- [[3],[0,2,1,4],2]
- Explanation
- Vehicle 0 (4 m) and vehicle 1 (5 m) share lane 0: 4 + 1 + 5 = 10 fills it exactly. Vehicle 2 (3 m) goes to lane 1, vehicle 3 (6 m) fits nowhere (3 + 1 + 6 > 6) and is refused, and vehicle 4 (2 m) still boards lane 1 (3 + 1 + 2 = 6). At stop 1, lane 0 holds [0, 1]: vehicle 0 is deepest, so vehicle 1 must shuffle (1). Lane 1 holds [2, 4]: vehicle 4 shuffles (1). Vehicle 0 and 2 leave, then at stop 2 vehicles 1 and 4 leave. Total 2 shuffles.
Example 2
- Input:
- [[8,8,6],[[8,2],[3,1],[4,1],[4,3],[3,1],[5,1],[1,2]]]
- Output:
- [[4,5],[2,1,0,6,3],0]
- Explanation
- Vehicle 0 fills lane 0 exactly (8 m, no gap for the first vehicle). Vehicles 1 and 2 share lane 1 (3 + 1 + 4 = 8) and vehicle 3 goes to lane 2. Vehicles 4 (3 m) and 5 (5 m) cannot fit anywhere and are refused, but vehicle 6 (1 m) fits lane 2 (4 + 1 + 1 = 6). At stop 1 both vehicles of lane 1 leave, nearest the ramp first (2 then 1), with no shuffles. Stop 2: vehicle 0, then vehicle 6. Stop 3: vehicle 3.
Example 3
- Input:
- [[30],[[5,1],[5,2],[5,1],[5,3],[5,2]]]
- Output:
- [[],[2,0,4,1,3],4]
- Explanation
- All five vehicles board the single lane. At stop 1 the deepest leaver is vehicle 0, so vehicles 1, 3 and 4 shuffle (3); vehicles 2 and 0 leave in that order. At stop 2 the lane is [1, 3, 4]; vehicle 1 is deepest, so vehicle 3 shuffles (1) and vehicle 4 plus vehicle 1 leave in that order. Vehicle 3 leaves at stop 3. Total 4 shuffles.
Constraints
- 1 ≤ lanes.length ≤ 8; 1 ≤ lanes[k] ≤ 40
- 0 ≤ vehicles.length ≤ 60; 1 ≤ length ≤ 45; 1 ≤ dest ≤ 9