Most Profitable Gigs
HardIntervals
Problem
A freelance sound engineer is offered several gigs. Gig i is [start, end, pay]: it occupies the half-open time range [start, end) and pays pay. She can work one gig at a time, and a gig ending at t leaves her free to start another at t.
Return the maximum total pay she can earn.
Example 1
- Input:
- gigs = [[1, 3, 50], [2, 4, 10], [3, 5, 40], [3, 6, 70]]
- Output:
- 120
Take [1, 3) for 50 and [3, 6) for 70.
Example 2
- Input:
- gigs = [[1, 2, 5], [2, 3, 6], [3, 4, 5], [2, 5, 20]]
- Output:
- 25
[1, 2) + [2, 5) pays 25, more than the three short gigs (16).
Constraints
- 1 ≤ gigs.length ≤ 5·10^4
- 0 ≤ start < end ≤ 10^9
- 1 ≤ pay ≤ 10^9
Hint
Show the first hint
Greedy by end time works when every gig pays the same. Why does it fail here?
Walkthrough
How to approach it
01Clarify before coding
- Can gigs that touch both be taken? Yes, ranges are half-open.
- Must she take at least one gig? Taking nothing pays 0, but every pay is positive, so the answer is at least the best single gig.
- How large can the total be? Up to 5·10^13: Python ints and JS doubles both hold it exactly.
02Brute force
Try every subset of gigs, keep the compatible ones and take the best total.
Cost: O(2^n · n) time: unusable beyond 20–25 gigs.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.