Optimize flight and cargo bookings for profit
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## OptiCargo: make the booking algorithm profitable
You are given two streams/lists:
- **Flights** you may attempt to book. Each flight has:
- `flight_id`
- `depart_time` and `arrive_time`
- `max_weight` (capacity)
- `cost` (paid only if you successfully book the flight)
- **Cargo jobs** you may book. Each cargo has:
- `cargo_id`
- `weight`
- `latest_arrival_time` (deadline)
- `revenue` (earned if delivered by the deadline)
A cargo job can be assigned to **at most one** booked flight. A flight can carry multiple cargo jobs as long as total assigned weight ≤ `max_weight`. A cargo job is deliverable on a flight if `arrive_time ≤ latest_arrival_time`.
### Task A (batch / fix existing code)
The existing implementation is unprofitable because it books **all** flights regardless of whether there is profitable cargo to carry.
Design/implement changes so that the algorithm chooses which flights to book and which cargo to assign to maximize **total profit**:
\[
\text{profit} = \sum(\text{revenue of delivered cargo}) - \sum(\text{cost of booked flights})
\]
You may output either:
- the maximum profit value, or
- the set of booked flights and cargo-to-flight assignments.
### Task B (incremental / streaming class)
Implement a class that processes events as they arrive:
- `onFlight(flight)` adds a new available flight.
- `onCargo(cargo)` adds a new available cargo job.
- Optionally, `decide()` (or similar) updates the plan.
At any time, the class should be able to report the current planned profit and/or current bookings/assignments.
### Realism constraint (booking may fail)
When you “apply” to book a flight, the booking can fail (e.g., another party booked it first). Your design should handle failed bookings gracefully (e.g., retry, re-plan, or treat it as removed from availability).
Quick Answer: This question evaluates resource allocation, combinatorial optimization, and online/streaming algorithm design within the Coding & Algorithms domain, requiring reasoning about assigning weight‑constrained cargo to flights under timing and cost constraints; it is commonly asked to assess algorithmic thinking about trade-offs between revenue and booking cost, constraint satisfaction, and handling dynamic inputs. The problem tests both conceptual understanding of optimization and online decision‑making and practical application skills for implementing incremental processing and robust handling of failed bookings.
Part 1: Maximize Opticargo profit for a fixed set of flights and cargo
Given a fixed set of **flights** and **cargo orders**, assign cargo to flights to **maximize total profit**. Each flight is a dedicated shipment slot that, if booked, carries **at most one** cargo order, and each cargo can be shipped on **at most one** flight.
Implement:
```python
def solution(flights, cargos):
```
## Input format
- **`flights`** — a list of flights. Each flight is a 3-element array `[departure_time, max_weight, cost]`:
- `departure_time` — when the flight departs
- `max_weight` — the most weight the flight can carry
- `cost` — the cost of booking the flight
- **`cargos`** — a list of cargo orders. Each cargo is a 3-element array `[weight, latest_arrival, revenue]`:
- `weight` — the cargo's weight
- `latest_arrival` — the latest time the cargo may arrive
- `revenue` — the revenue earned by delivering the cargo
Either list may be empty.
## Feasibility rule
In this simplified model **delivery is instantaneous**. A cargo `j` can be assigned to a flight `i` **if and only if** both conditions hold:
1. `flights[i].departure_time <= cargos[j].latest_arrival`
2. `flights[i].max_weight >= cargos[j].weight`
## Profit
If cargo `j` is assigned to flight `i`, that pairing contributes profit:
```
revenue_j - cost_i
```
## Rules
- You may **skip** any flight or any cargo — leaving a flight unbooked or a cargo unshipped contributes `0`.
- **Never take a loss-making booking when skipping is better.** Because skipping is always allowed, a feasible pair whose `revenue_j - cost_i` is **not positive** should never be booked (it contributes `0`, same as skipping).
- A flight can be matched to at most one cargo, and a cargo to at most one flight (the assignment is a one-to-one matching between a subset of flights and a subset of cargos).
## Output
Return the **maximum total profit** achievable over all valid assignments, as an integer. If no profitable booking exists (including when either list is empty), return `0`.
## Constraints
- `0 <= len(flights), len(cargos) <= 80`
- `1 <= departure_time, latest_arrival, max_weight, weight, cost, revenue <= 10^9`
- Each flight can be used at most once.
- Each cargo can be shipped at most once.
Constraints
- 0 <= len(flights), len(cargos) <= 80
- 1 <= departure_time, latest_arrival, max_weight, weight, cost, revenue <= 10^9
- Each flight can be used at most once
- Each cargo can be shipped at most once
Examples
Input: ([(1, 10, 100), (3, 5, 30)], [(4, 3, 90), (5, 1, 120), (6, 5, 140)])
Expected Output: 100
Explanation: Assign cargo (4, 3, 90) to flight (3, 5, 30) for profit 60, and cargo (6, 5, 140) to flight (1, 10, 100) for profit 40. Total profit is 100.
Input: ([(2, 3, 50)], [(4, 5, 100), (3, 1, 100)])
Expected Output: 0
Explanation: One cargo is too heavy and the other misses the time constraint, so no profitable shipment is possible.
Input: ([(1, 5, 70), (2, 5, 10)], [(5, 2, 60), (5, 2, 50)])
Expected Output: 50
Explanation: The first flight loses money on every feasible cargo, so only the second flight should be used.
Input: ([(2, 10, 20), (1, 5, 5)], [(5, 2, 40), (10, 2, 50)])
Expected Output: 65
Explanation: Best is to use both flights: profit 35 from matching the smaller flight with the 5-weight cargo, and profit 30 from matching the larger flight with the 10-weight cargo.
Input: ([], [(1, 1, 10)])
Expected Output: 0
Explanation: No flights means no shipments.
Solution
def solution(flights, cargos):
n_f = len(flights)
n_c = len(cargos)
n = max(n_f, n_c)
if n == 0:
return 0
profit = [[0] * n for _ in range(n)]
max_cell = 0
for i, (depart, max_weight, cost) in enumerate(flights):
for j, (weight, latest_arrival, revenue) in enumerate(cargos):
if depart <= latest_arrival and max_weight >= weight:
value = revenue - cost
if value > 0:
profit[i][j] = value
if value > max_cell:
max_cell = value
cost_matrix = [[max_cell - profit[i][j] for j in range(n)] for i in range(n)]
u = [0] * (n + 1)
v = [0] * (n + 1)
p = [0] * (n + 1)
way = [0] * (n + 1)
for i in range(1, n + 1):
p[0] = i
j0 = 0
minv = [float('inf')] * (n + 1)
used = [False] * (n + 1)
while True:
used[j0] = True
i0 = p[j0]
delta = float('inf')
j1 = 0
for j in range(1, n + 1):
if not used[j]:
cur = cost_matrix[i0 - 1][j - 1] - u[i0] - v[j]
if cur < minv[j]:
minv[j] = cur
way[j] = j0
if minv[j] < delta:
delta = minv[j]
j1 = j
for j in range(n + 1):
if used[j]:
u[p[j]] += delta
v[j] -= delta
else:
minv[j] -= delta
j0 = j1
if p[j0] == 0:
break
while True:
j1 = way[j0]
p[j0] = p[j1]
j0 = j1
if j0 == 0:
break
assignment = [-1] * n
for j in range(1, n + 1):
if p[j] != 0:
assignment[p[j] - 1] = j - 1
answer = 0
for i in range(n_f):
j = assignment[i]
if 0 <= j < n_c:
answer += profit[i][j]
return answerExplanation
This is a **maximum-weight bipartite matching** problem: flights on one side, cargos on the other, and we want to pick disjoint flight→cargo pairs maximizing total profit. The code solves it with the **Hungarian algorithm** (Kuhn–Munkres, O(n³) potentials variant).
**Step 1 — build the profit matrix.** For every flight `(depart, max_weight, cost)` and cargo `(weight, latest_arrival, revenue)`, the pair is *feasible* iff `depart <= latest_arrival` and `max_weight >= weight`. The pair's value is `revenue - cost`, but it is recorded **only if positive** — a loss-making booking is treated exactly like an infeasible one (profit stays `0`), which is correct because skipping is always allowed.
**Step 2 — convert max-profit to min-cost on a square matrix.** Both sides are padded to `n = max(len(flights), len(cargos))`, and each entry becomes `cost = max_cell - profit`. Because the best profit maps to cost `0` and any skip/loss cell maps to the largest cost (`max_cell`), minimizing total cost over a *perfect* matching is equivalent to maximizing total profit. Padding rows/columns carry profit `0`, so matching a real flight to a phantom cargo costs the same as leaving it unbooked — the algorithm freely declines bad assignments.
**Step 3 — run Hungarian.** The `u`/`v` dual potentials, `p` (column→row matching), and `way` (augmenting-path predecessors) implement the standard one-row-at-a-time augmentation. After solving, `assignment[i] = j` recovers each flight's matched column.
**Step 4 — sum real profit.** Only pairs where both `i < len(flights)` and `j < len(cargos)` (i.e. not padding) and with positive stored profit contribute, giving the maximum total profit.
It's correct because the Hungarian algorithm returns a provably optimal min-cost perfect matching, and the `0`-profit encoding makes "skip" a free, optimal-preserving choice.
Time complexity: O(F * C + N^3), where F = len(flights), C = len(cargos), N = max(F, C). Building the profit matrix is O(F*C); the Hungarian algorithm runs N augmentation rounds, each O(N^2), giving O(N^3).. Space complexity: O(N^2) for the profit and cost matrices, where N = max(F, C). The Hungarian bookkeeping arrays (u, v, p, way, minv, used) are O(N)..
Hints
- Think of flights and cargo orders as the two sides of a bipartite graph. A feasible pair has weight max(0, revenue - cost).
- Because skipping is allowed, you can add dummy nodes with profit 0 and solve a maximum-weight matching problem.
Part 2: Streaming Opticargo planner with updates and profit queries
Build a **streaming cargo-to-flight profit planner**: process a list of `operations` that arrive over time and, for every `QUERY` operation, return the **current maximum total profit** achievable by assigning the active cargos to the active flights.
## What to implement
```python
def solution(operations):
...
```
`operations` is a list of operations (each is a tuple/list whose first element is the operation name). Return a list of integers — **one answer per `QUERY`**, in the order the queries occur.
## State
You maintain two collections that change as operations are processed:
- **Active flights**, each identified by a string `flight_id`.
- **Active cargos**, each identified by a string `cargo_id`.
## Operations
Each operation is one of the following (argument order matters):
| Operation | Form | Effect |
|-----------|------|--------|
| Add flight | `('ADD_FLIGHT', flight_id, departure_time, max_weight, cost)` | Make the flight active. |
| Add cargo | `('ADD_CARGO', cargo_id, weight, latest_arrival, revenue)` | Make the cargo active. |
| Remove flight | `('REMOVE_FLIGHT', flight_id)` | Make that flight inactive. |
| Remove cargo | `('REMOVE_CARGO', cargo_id)` | Make that cargo inactive. |
| Query | `('QUERY',)` | Append the current maximum total profit to the output. |
**Update semantics:**
- **Re-adding an existing id replaces** the previously active record that has the same id (the newest attributes win).
- **Removing a non-existent id is a no-op** (do nothing, no error).
## Shipment model (same as Part 1)
At any query, you assign cargos to flights subject to:
- **Each active flight carries at most one active cargo**, and **each active cargo uses at most one flight** (a one-to-one matching). Any flight or cargo may also be left unassigned.
- A cargo can be carried by a flight **only if both** of the following hold:
- `departure_time <= latest_arrival`, and
- `max_weight >= weight`.
- The **profit** of carrying a cargo on a flight is `revenue - cost`.
A match whose profit is **not positive** (`revenue - cost <= 0`) is never worth making and should be treated as contributing **0** — equivalently, only assign a cargo to a flight when doing so strictly increases total profit.
The answer for a query is the **maximum total profit** over all valid assignments of the current active flights and cargos. If there are no profitable matches (or no active flights/cargos), the answer is **0**.
## Output
Return the list of query answers in order. The maximum total profit is always `>= 0`.
## Constraints
- `0 <= len(operations) <= 200`
- At any `QUERY`, the number of active flights and the number of active cargos are each at most `60`.
- `1 <= departure_time, latest_arrival, max_weight, weight, cost, revenue <= 10^9`
- `flight_id` and `cargo_id` are strings.
- Re-adding an existing id replaces the previously active item with that id.
## Example
```
operations = [
('ADD_FLIGHT', 'F1', 1, 10, 100),
('ADD_CARGO', 'C1', 4, 3, 90),
('QUERY',), -> 0
('ADD_CARGO', 'C2', 6, 5, 140),
('QUERY',), -> 40
('ADD_FLIGHT', 'F2', 3, 5, 30),
('QUERY',), -> 100
]
# returns [0, 40, 100]
```
At the first query, only F1 and C1 are active: F1 can carry C1 (`1 <= 3` and `10 >= 4`), but the profit is `90 - 100 = -10`, which is not positive, so the best total is `0`. After adding C2, F1 can carry C2 for `140 - 100 = 40`. After adding F2, F1↔C2 (`40`) plus F2↔C1 (`90 - 30 = 60`) gives a total of `100`.
Constraints
- 0 <= len(operations) <= 200
- At any QUERY, the number of active flights and active cargos is at most 60 each
- 1 <= departure_time, latest_arrival, max_weight, weight, cost, revenue <= 10^9
- flight_id and cargo_id are strings
- Re-adding an existing id replaces the previous active item
Examples
Input: [('ADD_FLIGHT', 'F1', 1, 10, 100), ('ADD_CARGO', 'C1', 4, 3, 90), ('QUERY',), ('ADD_CARGO', 'C2', 6, 5, 140), ('QUERY',), ('ADD_FLIGHT', 'F2', 3, 5, 30), ('QUERY',)]
Expected Output: [0, 40, 100]
Explanation: With only F1 and C1, shipping loses money so the best profit is 0. After adding C2, F1 can profitably ship it for 40. After adding F2, the best matching becomes 100.
Input: [('ADD_FLIGHT', 'F1', 1, 5, 5), ('ADD_FLIGHT', 'F2', 2, 10, 20), ('ADD_CARGO', 'C1', 5, 2, 40), ('ADD_CARGO', 'C2', 10, 2, 50), ('QUERY',), ('REMOVE_CARGO', 'C2'), ('QUERY',), ('REMOVE_FLIGHT', 'F1'), ('QUERY',)]
Expected Output: [65, 35, 20]
Explanation: The best matching first uses both flights. After removing C2, only C1 remains and F1 is the better choice. After removing F1, only F2 can ship C1.
Input: [('QUERY',)]
Expected Output: [0]
Explanation: Querying an empty system should return 0.
Input: [('ADD_FLIGHT', 'F1', 5, 5, 10), ('ADD_CARGO', 'C1', 5, 4, 100), ('QUERY',), ('ADD_FLIGHT', 'F1', 3, 5, 10), ('QUERY',), ('REMOVE_CARGO', 'NOPE'), ('REMOVE_FLIGHT', 'F1'), ('QUERY',)]
Expected Output: [0, 90, 0]
Explanation: The first version of F1 is too late for C1, then re-adding F1 replaces it with a feasible version. Removing a non-existent cargo is ignored.
Solution
def solution(operations):
def max_profit(flights, cargos):
n_f = len(flights)
n_c = len(cargos)
n = max(n_f, n_c)
if n == 0:
return 0
profit = [[0] * n for _ in range(n)]
max_cell = 0
for i, (depart, max_weight, cost) in enumerate(flights):
for j, (weight, latest_arrival, revenue) in enumerate(cargos):
if depart <= latest_arrival and max_weight >= weight:
value = revenue - cost
if value > 0:
profit[i][j] = value
if value > max_cell:
max_cell = value
cost_matrix = [[max_cell - profit[i][j] for j in range(n)] for i in range(n)]
u = [0] * (n + 1)
v = [0] * (n + 1)
p = [0] * (n + 1)
way = [0] * (n + 1)
for i in range(1, n + 1):
p[0] = i
j0 = 0
minv = [float('inf')] * (n + 1)
used = [False] * (n + 1)
while True:
used[j0] = True
i0 = p[j0]
delta = float('inf')
j1 = 0
for j in range(1, n + 1):
if not used[j]:
cur = cost_matrix[i0 - 1][j - 1] - u[i0] - v[j]
if cur < minv[j]:
minv[j] = cur
way[j] = j0
if minv[j] < delta:
delta = minv[j]
j1 = j
for j in range(n + 1):
if used[j]:
u[p[j]] += delta
v[j] -= delta
else:
minv[j] -= delta
j0 = j1
if p[j0] == 0:
break
while True:
j1 = way[j0]
p[j0] = p[j1]
j0 = j1
if j0 == 0:
break
assignment = [-1] * n
for j in range(1, n + 1):
if p[j] != 0:
assignment[p[j] - 1] = j - 1
answer = 0
for i in range(n_f):
j = assignment[i]
if 0 <= j < n_c:
answer += profit[i][j]
return answer
active_flights = {}
active_cargos = {}
answers = []
for op in operations:
kind = op[0]
if kind == 'ADD_FLIGHT':
_, flight_id, depart, max_weight, cost = op
active_flights[flight_id] = (depart, max_weight, cost)
elif kind == 'ADD_CARGO':
_, cargo_id, weight, latest_arrival, revenue = op
active_cargos[cargo_id] = (weight, latest_arrival, revenue)
elif kind == 'REMOVE_FLIGHT':
_, flight_id = op
active_flights.pop(flight_id, None)
elif kind == 'REMOVE_CARGO':
_, cargo_id = op
active_cargos.pop(cargo_id, None)
elif kind == 'QUERY':
answers.append(max_profit(list(active_flights.values()), list(active_cargos.values())))
else:
raise ValueError('Unknown operation: ' + str(kind))
return answersExplanation
This is **streaming maximum-profit bipartite matching**. We keep two dicts, `active_flights` and `active_cargos`, keyed by id. Because each id maps to one record, an `ADD_*` of an existing id naturally **replaces** the old record, and `REMOVE_*` uses `pop(id, None)` so removing a missing id is a no-op. Each `QUERY` recomputes the answer from scratch over the current active sets.
**Building the matching problem.** For every (flight, cargo) pair we create an edge only when the flight can carry the cargo: `depart <= latest_arrival` **and** `max_weight >= weight`. Its value is `revenue - cost`, kept in `profit[i][j]` only when **positive** — a money-losing match is never worth making, so it stays 0. Since each flight carries at most one cargo and vice-versa, the optimum is the maximum-weight matching of this bipartite graph.
**Solving via the Hungarian algorithm.** The Jonker–Volgenant routine here *minimizes* cost over a square `n×n` matrix (`n = max(#flights, #cargos)`), so we convert maximization to minimization with `cost = max_cell - profit` and pad with zero-profit cells. The inner `while`/`for` loops are the standard potential-based (`u`, `v`) augmenting-path search that produces a perfect assignment `p[]`.
**Reading the answer.** From the perfect assignment we sum only `profit[i][j]` for real indices (`i < n_f`, `j < n_c`). Padding cells and infeasible/non-positive cells contribute 0, and any item is free to "park" on a zero cell instead of taking a bad edge — so the recovered total is exactly the maximum achievable profit. Empty state returns 0.
Time complexity: O(Q * (A^3 + F*C)), where Q = number of QUERY ops, A = max(active flights, active cargos) at that query (<= 60), and F, C the active counts. Per query: O(F*C) to build the profit matrix and O(A^3) for the Hungarian assignment (the dominant term).. Space complexity: O(A^2) per query for the n*n profit and cost matrices (A = max(#flights, #cargos)); the potential/path arrays (u, v, p, way, minv, used) are O(A). Plus O(F + C) for the active-id dictionaries..
Hints
- Keep the currently active flights and cargos in dictionaries keyed by id.
- Because the active set is small, you can recompute the best offline matching from scratch on every QUERY.