Optimize flight and cargo bookings for profit

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).

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:

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.

Examples

Example 1

Input: ([(1, 10, 100), (3, 5, 30)], [(4, 3, 90), (5, 1, 120), (6, 5, 140)])
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.

Example 2

Input: ([(2, 3, 50)], [(4, 5, 100), (3, 1, 100)])
Output: 0

Explanation: One cargo is too heavy and the other misses the time constraint, so no profitable shipment is possible.

Hints

1. Think of flights and cargo orders as the two sides of a bipartite graph. A feasible pair has weight max(0, revenue - cost).
2. Because skipping is allowed, you can add dummy nodes with profit 0 and solve a maximum-weight matching problem.

Approach

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).

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

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.

Hints

1. Keep the currently active flights and cargos in dictionaries keyed by id.
2. Because the active set is small, you can recompute the best offline matching from scratch on every QUERY.

Approach

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 + FC)), 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(FC) 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.