progress

~/problems / 1-D dynamic programming / Intro DP

Maximum Profit in Job Scheduling

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~45 min AmazonGoogle

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^9 and 1 <= 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.

Topic: Intro DP. State, transition, base case; top-down memo vs bottom-up table.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc