Maximize Value from Event Stream

Problem Events arrive as [id, time, amount] and you have a fixed total time budget (e.g. 60s). Pick a subset of events maximizing total amount subject to Σ time ≤ budget. There is no ordering constraint, so this is 0/1 knapsack.

Input / Output

• Input: events (each a time cost and an amount value) and an integer budget.
• Output: the maximum total amount (optionally the chosen ids).

Constraints

• Feasibility depends on the budget: O(n · budget) DP works for integer budgets up to a few thousand; very large budgets with small n call for meet-in-the-middle.

Example

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