Pick non-overlapping trades for maximum profit

Question

Each candidate trade has a start time, an end time, and a profit. Only one trade can run at a time (windows must not overlap; touching endpoints are allowed). Choose a set of compatible trades that maximizes total profit.

trades = [(1,3,50), (2,5,20), (4,6,70), (6,7,30)]   # (start, end, profit)
-> 150      # (1,3,50) + (4,6,70) + (6,7,30)

Return the maximum achievable profit (weighted interval scheduling). Greedily grabbing the biggest profit or the earliest finish can be suboptimal.

Accepted Answer

Sort trades by end time. Let dp[i] be the best profit using the first i trades. For trade i, either skip it (dp[i-1]) or take it and jump back to the last trade that finishes no later than this one starts. Since ends are sorted, a binary search finds that predecessor quickly. Tracing the example, dp becomes [0, 50, 50, 120, 150], so the answer is 150. Time O(n log n), space O(n). Edge cases: an empty list returns 0; if you treat touching endpoints as a conflict, use bisectleft (strictly-before ends) instead of bisectright. Takeaway. Weighted interval scheduling is the profit-carrying cousin o…

Pick non-overlapping trades for maximum profit

Your answer

More Coding questions