826. Most Profit Assigning Work | 1709
I have no idea why this is also 1709. It feels very intuitive and straightforward. I might just be good at greedy problems.
I hate myself for losing my leetcode streak tho.
Now that my repo is temporarily private (and likely won’t publicize soon)…
1class Solution:
2 def maxProfitAssignment(
3 self, difficulty: List[int], profit: List[int], worker: List[int]
4 ) -> int:
5 # intuition:
6 # sort difficulty with key = profit
7 # go through, if a tougher job has a lower profit del it
8 # bi search for each worker
9
10 diff_prof = []
11 for i in range(len(difficulty)):
12 diff_prof.append((profit[i], difficulty[i]))
13 diff_prof.sort()
14
15 meaningful_work = deque([(-1, -1)])
16 for p, d in diff_prof:
17 while d <= meaningful_work[-1][1]:
18 meaningful_work.pop()
19 meaningful_work.append((p, d))
20 meaningful_work.popleft()
21
22 ndiff = []
23 nprof = []
24 for p, d in meaningful_work:
25 ndiff.append(d)
26 nprof.append(p)
27
28 result = 0
29 for w in worker:
30 i = bisect_right(ndiff, w)
31 if i != 0:
32 result += nprof[i - 1]
33
34 return result
#Array #Binary-Search #Greedy #Sorting #Python