Loading page…
Practice problem · hard
A parcel-delivery app has a job board for couriers. Each job runs from a start minute up to, but not including, an end minute, and it pays a fixed amount. A courier can do one job at a time, but may start a job at the minute the last one ends.
You get all the jobs. Find the largest total pay the courier can earn from jobs that do not overlap.
Write best_profit(start, end, profit).
i runs from start[i] up to, but not including, end[i], with start[i] < end[i], and pays profit[i].Input: start = [1, 2, 3, 3], end = [3, 4, 5, 6], profit = [50, 10, 40, 70]
Output: 120Sort the jobs by end. For each job, the best total is the larger of two choices. Skip the job, or take it and add the best total of the jobs that end by its start.
| Job (start, end, pay) | Best total before it that ends by its start | Take it | Skip it | Best so far |
|---|---|---|---|---|
| (1, 3, 50) | 0 | 50 | 0 | 50 |
| (2, 4, 10) | 0 | 10 | 50 | 50 |
| (3, 5, 40) | 50 | 90 | 50 | 90 |
| (3, 6, 70) | 50 | 120 | 90 | 120 |
The best plan takes the jobs (1, 3) and (3, 6), for 120.
Input: start = [1, 1, 1], end = [2, 3, 4], profit = [5, 6, 4]
Output: 6All three jobs start at minute 1, so only one can be done. The best pays 6.
Input: start = [1, 3], end = [3, 5], profit = [5, 5]
Output: 10The second job starts at minute 3, exactly when the first ends, so both can be done.
0 ≤ start.length = end.length = profit.length ≤ 100,000 (jobs)1 ≤ start[i] < end[i] ≤ 1,000,000,000 (minutes)1 ≤ profit[i] ≤ 10,000Trying every set of jobs means 2^n sets, which is impossible even for n = 60. Sorting costs n log n, and one pass with a binary search for each job costs n log n.
best_profit · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.