Cargo Order Allocation Across Departing Planes
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A freight company assigns incoming shipping orders to a fixed fleet of cargo planes. You must implement the order-processing logic: decide whether each order can be accepted, and if so, allocate its cargo across planes and update the fleet's remaining capacity.
You are given `planes`, where `planes[i] = [departure_i, capacity_i]`: plane `i` departs at time `departure_i` and can carry at most `capacity_i` units of cargo. Each plane's departure time and capacity are fixed; its remaining capacity only decreases as cargo is assigned to it and never resets.
Orders arrive as a sequence and must be processed strictly in the given order. `orders[j] = [time_j, items_j]`, where `time_j` is the time the order is placed and `items_j` is a non-empty list of positive integers — the sizes of the cargo pieces in the order. Let `total_j` be the sum of `items_j`.
**Rules**
1. **Eligibility:** cargo from order `j` may only be loaded onto planes that depart **strictly after** `time_j` (a plane with `departure_i > time_j`).
2. **Splitting:** cargo is divisible — an order's cargo may be split across multiple eligible planes in integer units. Individual piece boundaries do not restrict the split; only the order's total size `total_j` matters for allocation.
3. **Acceptance:** order `j` is accepted if and only if, at the moment it is processed, the sum of the remaining capacities of all eligible planes is at least `total_j`.
4. **All-or-nothing:** if an order is rejected, no plane's remaining capacity changes. A rejected order is never retried.
5. **Allocation policy (deterministic):** when an order is accepted, fill eligible planes in ascending order of departure time, breaking ties by ascending plane index. Assign to each such plane `min(remaining cargo to place, plane's remaining capacity)` units, skipping planes whose remaining capacity is `0`, until the full `total_j` units are placed. Then commit the capacity updates.
**Output**
Return an array `result` with one element per order, in input order:
- If order `j` is **rejected**, `result[j]` is an empty array `[]`.
- If order `j` is **accepted**, `result[j]` is an array of `[i, amount]` pairs — plane index and the number of units assigned to that plane — listed in the order the planes were filled, including only planes that received `amount > 0`.
**Example**
```
planes = [[5, 10], [10, 8], [3, 6]]
orders = [[2, [4, 5]], [4, [12]], [6, [9]], [0, [30]]]
```
- Order 0 (time 2, total 9): eligible planes (departure > 2) are 0, 1, 2. Fill by ascending departure: plane 2 (departs 3) takes 6, plane 0 (departs 5) takes 3. Result: `[[2, 6], [0, 3]]`. Remaining capacities: plane 0 → 7, plane 1 → 8, plane 2 → 0.
- Order 1 (time 4, total 12): eligible planes are 0 (7 left) and 1 (8 left); 7 + 8 = 15 ≥ 12, accepted. Plane 0 takes 7, plane 1 takes 5. Result: `[[0, 7], [1, 5]]`. Remaining: plane 0 → 0, plane 1 → 3.
- Order 2 (time 6, total 9): only plane 1 is eligible (departs 10) with 3 left; 3 < 9, rejected. Result: `[]`. State unchanged.
- Order 3 (time 0, total 30): all planes eligible, remaining sum is 0 + 3 + 0 = 3 < 30, rejected. Result: `[]`.
```
result = [[[2, 6], [0, 3]], [[0, 7], [1, 5]], [], []]
```
**Constraints**
- `1 <= planes.length <= 2 * 10^5`
- `1 <= orders.length <= 2 * 10^5`
- The total number of cargo pieces across all orders is at most `4 * 10^5`.
- `0 <= departure_i, time_j <= 10^9`
- `1 <= capacity_i <= 10^9`; each cargo piece size is between `1` and `10^9`.
- All capacity and cargo sums fit in a signed 64-bit integer.
- Orders must be processed in the given sequence; each order's acceptance decision uses the fleet state left by all previous orders.
A solution that re-scans and re-sorts the whole fleet for every order will be too slow for the largest inputs; aim for roughly `O((n + m) log n)` overall, where `n` is the number of planes and `m` is the number of orders.
Quick Answer: This question evaluates competence in deterministic resource allocation, stateful simulation, and capacity-management under time constraints, exercising algorithmic reasoning and data-structure handling within the Coding & Algorithms domain.
A freight company assigns incoming shipping orders to a fixed fleet of cargo planes. Implement the order-processing logic: decide whether each order can be accepted and, if so, allocate its cargo across planes and update remaining capacity.
You are given `planes`, where `planes[i] = [departure_i, capacity_i]`: plane `i` departs at time `departure_i` and can carry at most `capacity_i` units of cargo. A plane's departure time and capacity are fixed; its remaining capacity only decreases as cargo is assigned and never resets.
Orders are processed strictly in the given order. For order `j`, `order_times[j]` is the time it is placed and `order_items[j]` is a non-empty list of positive integers — the sizes of the cargo pieces. Let `total_j` be the sum of `order_items[j]`.
Implement `solution(planes, order_times, order_items)` and return `result`, one entry per order.
**Rules**
1. **Eligibility:** cargo from order `j` may only be loaded onto planes that depart **strictly after** `order_times[j]` (a plane with `departure_i > order_times[j]`).
2. **Splitting:** cargo is divisible — an order's cargo may be split across multiple eligible planes in integer units. Piece boundaries do not restrict the split; only the total `total_j` matters.
3. **Acceptance:** order `j` is accepted iff, at the moment it is processed, the sum of the remaining capacities of all eligible planes is at least `total_j`.
4. **All-or-nothing:** if an order is rejected, no plane's remaining capacity changes. A rejected order is never retried.
5. **Allocation policy (deterministic):** when an order is accepted, fill eligible planes in ascending order of departure time, breaking ties by ascending plane index. Assign each such plane `min(remaining cargo to place, plane's remaining capacity)` units, skipping planes whose remaining capacity is `0`, until all `total_j` units are placed. Then commit the updates.
**Output**
- If order `j` is **rejected**, `result[j]` is an empty array `[]`.
- If order `j` is **accepted**, `result[j]` is an array of `[i, amount]` pairs — plane index and units assigned — in the order planes were filled, including only planes that received `amount > 0`.
**Example**
```
planes = [[5, 10], [10, 8], [3, 6]]
order_times = [2, 4, 6, 0]
order_items = [[4, 5], [12], [9], [30]]
```
- Order 0 (time 2, total 9): eligible planes 0, 1, 2. Fill by ascending departure: plane 2 (departs 3) takes 6, plane 0 (departs 5) takes 3 -> `[[2, 6], [0, 3]]`. Remaining: 7, 8, 0.
- Order 1 (time 4, total 12): eligible 0 (7) and 1 (8); 15 >= 12, accepted. Plane 0 takes 7, plane 1 takes 5 -> `[[0, 7], [1, 5]]`. Remaining: 0, 3, 0.
- Order 2 (time 6, total 9): only plane 1 eligible with 3 left; 3 < 9, rejected -> `[]`.
- Order 3 (time 0, total 30): remaining sum 0 + 3 + 0 = 3 < 30, rejected -> `[]`.
```
result = [[[2, 6], [0, 3]], [[0, 7], [1, 5]], [], []]
```
**Constraints**
- `1 <= planes.length <= 2 * 10^5`
- `1 <= order_times.length == order_items.length <= 2 * 10^5`
- Total cargo pieces across all orders <= `4 * 10^5`.
- `0 <= departure_i, time_j <= 10^9`; `1 <= capacity_i <= 10^9`; each piece size in `[1, 10^9]`.
- All capacity and cargo sums fit in a signed 64-bit integer.
- A solution that re-sorts the whole fleet per order is too slow; aim for roughly `O((n + m) log n)`.
Constraints
- 1 <= planes.length <= 2 * 10^5
- 1 <= order_times.length == order_items.length <= 2 * 10^5
- Total cargo pieces across all orders <= 4 * 10^5
- 0 <= departure_i, time_j <= 10^9
- 1 <= capacity_i <= 10^9 and each cargo piece size is in [1, 10^9]
- All capacity and cargo sums fit in a signed 64-bit integer
- Orders are processed strictly in input order; each decision uses the state left by prior orders
Examples
Input: ([[5, 10], [10, 8], [3, 6]], [2, 4, 6, 0], [[4, 5], [12], [9], [30]])
Expected Output: [[[2, 6], [0, 3]], [[0, 7], [1, 5]], [], []]
Explanation: The worked example. Order 0 fills plane 2 (departs 3) then plane 0 (departs 5). Order 1 exhausts plane 0 then partially fills plane 1. Order 2 and order 3 lack enough eligible remaining capacity and are rejected, leaving state unchanged.
Input: ([[5, 10]], [3], [[10]])
Expected Output: [[[0, 10]]]
Explanation: Single plane departs at 5 > 3, so it is eligible with 10 units. The order total is exactly 10, so it is accepted and fully loaded onto plane 0.
Hints
- Eligibility, acceptance, and the fill order all key off departure time, so pre-sort plane indices once by (departure, index). Within an order, eligible planes are exactly the suffix of that sorted order whose departure is strictly greater than the order's time — find its start with a binary search.
- Acceptance is purely a capacity-sum test over that eligible suffix, and it is the SAME suffix you then fill. Accept iff the summed remaining capacity of the suffix is at least the order total; only mutate capacities after you have confirmed acceptance (all-or-nothing).
- Fill greedily along the suffix in (departure, index) order, giving each plane min(remaining_to_place, plane_capacity) and skipping planes already at 0. To beat the O(n) per-order scan at scale, maintain remaining capacity in a Fenwick/segment tree over departure rank so both the suffix sum and the walk to the next non-empty plane are O(log n).