Loading page…
Practice problem · medium
A delivery app posts routes for the day. Each route has a difficulty rating and a fixed pay. A driver has a skill level and can take any route whose difficulty is at most that skill.
Many drivers may take the same route. Each driver picks the best-paying route they can handle, or earns nothing if none fits. You are asked for the total pay the app owes all its drivers today.
Write total_best_pay(difficulty, pay, skills).
i has difficulty difficulty[i] and pay pay[i]. The lists have the same length, and routes are not sorted.skills[d] is the skill of driver d. The drivers are not sorted either.s can take route i when difficulty[i] <= s. A route can be taken by any number of drivers.Input: difficulty = [4, 10, 2, 7, 5], pay = [30, 90, 20, 25, 60], skills = [3, 8, 5, 1]
Output: 140Sort the routes by difficulty: (2, 20), (4, 30), (5, 60), (7, 25), (10, 90). Sort the skills: 1, 3, 5, 8. A pointer k opens routes in that order, and best is the best pay among the routes opened so far.
| Driver skill | Routes opened | best | Pay added | Total after |
|---|---|---|---|---|
| 1 | none: the easiest route has difficulty 2 | 0 | 0 | 0 |
| 3 | (2, 20) | 20 | 20 | 20 |
| 5 | (4, 30), (5, 60) | 60 | 60 | 80 |
| 8 | (7, 25): pays less than 60 | 60 | 60 | 140 |
The route with difficulty 7 is harder than the one with difficulty 5, but it pays less. The driver with skill 8 still takes the route that pays 60.
Input: difficulty = [6], pay = [40], skills = [6, 6, 6]
Output: 120A skill equal to the difficulty is enough, and the route is shared: three drivers earn 40 each.
Input: difficulty = [5, 9], pay = [10, 20], skills = [4, 2]
Output: 0Both drivers are below the easiest route, so nobody earns anything.
1 ≤ difficulty.length = pay.length ≤ 100,000 (routes)1 ≤ skills.length ≤ 100,000 (drivers)1 ≤ difficulty[i], pay[i], skills[d] ≤ 100,000Checking every route for every driver costs n × m checks. With 100,000 routes and 100,000 drivers that is 10^10, about 100 seconds at 10^8 operations a second. Sorting both lists costs about 1.7 million steps each, and one sweep adds 200,000 more.
The total can reach 100,000 × 100,000 = 10^10. That does not fit in 32 bits, so use a 64-bit integer.
total_best_pay · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.