Maximize Value from Event Stream

Problem Events arrive as [id, time, amount] with a fixed total time budget (e.g. 60s). Pick a subset maximizing total amount with Σ time <= budget — no ordering constraints, so it's 0/1 knapsack.

Input / Output

• Input: events (time cost, amount value), int budget. Output: max total amount (optionally the chosen ids).

Constraints

• Feasibility hinges on budget size: O(n · budget) DP works for integer budgets in the thousands; huge budgets → meet-in-the-middle for small n.

Example

• events = [[1,10,60],[2,20,100],[3,30,120]], budget = 50 → 220 (events 2 and 3) — the classic knapsack instance.

Expected approach

• 0/1 knapsack DP over budget: dp[w] = best amount using <= w time; iterate events, w from budget DOWN to time_i (descending order is what enforces single use — say why): dp[w] = max(dp[w], dp[w−t] + a). O(n·budget) time, O(budget) space; reconstruct picks with a parent/choice table. Spotting the reduction — no sequencing constraint ⇒ knapsack, not scheduling — is the primary signal; contrast with weighted interval scheduling where times DO overlap-constrain.