A freelance sound engineer has a list of gig offers. Gig i starts at time starts[i], ends at time ends[i] and pays pays[i]. She can only work one gig at a time, so she can't accept two gigs whose times overlap. A gig that ends at time t doesn't clash with one that starts at t: she can go straight from one to the next.
Write max_profit(starts, ends, pays) -> int that returns the most she can earn from the gigs she accepts.
max_profit([1, 2, 4, 6, 5], [3, 5, 6, 9, 8], [20, 30, 25, 45, 15])
# 90 (1-3, then 4-6, then 6-9: 20 + 25 + 45)
max_profit([1, 2, 3], [2, 3, 4], [5, 6, 7])
# 18 (all three, back to back)
max_profit([1, 2, 3, 4], [10, 3, 4, 5], [100, 30, 30, 30])
# 100 (the long gig beats the three short ones it overlaps)
In the first example, taking the best-paying gig first (6-9 for 45) and then the next best that still fits (2-5 for 30) only reaches 75.
Constraints:
n = len(starts) == len(ends) == len(pays),1 <= n <= 10^5.0 <= starts[i] < ends[i] <= 10^9and1 <= pays[i] <= 10^9. The total can exceed 32 bits (use 64-bit integers in C++/Java).- The gigs come in no particular order.
- ⭐ Bonus: comparing every gig with every other gig is O(n²) and still passes; a speed test with 100,000 gigs earns a star in O(n log n).
Show hint
Sort the gigs by end time and ask, for the first i gigs in that order, what the best total is. Gig i is either skipped or taken. If it's taken, everything else must come from gigs that end by its start time, and in the sorted order those form a prefix you can find with binary search.