Most Profit Assigning Work Python Solution

LeetCode 826, Medium. Topics: Array, Two Pointers, Binary Search, Greedy, Sorting. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 826   # by problem number
lcpy gen -s most_profit_assigning_work   # by problem name

Problem

You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:

difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if three workers attempt the same job that pays $1, then the total profit will be$ 3. If a worker cannot complete any job, their profit is $0.

Return the maximum profit we can achieve after assigning the workers to the jobs.

Examples

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0

Constraints

n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 10^4
1 <= difficulty[i], profit[i], worker[i] <= 10^5

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

import bisect


class Solution:
    # Time: O(n log n + m log n)
    # Space: O(n)
    def max_profit_assignment(
        self, difficulty: list[int], profit: list[int], worker: list[int]
    ) -> int:
        pairs = sorted(zip(difficulty, profit, strict=True))
        diffs = [d for d, _ in pairs]
        best: list[int] = []
        top = 0
        for _d, p in pairs:
            top = max(top, p)
            best.append(top)
        total = 0
        for ability in worker:
            i = bisect.bisect_right(diffs, ability)
            if i > 0:
                total += best[i - 1]
        return total

Complexity

Time	Space
O(n log n + m log n)	O(n)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Most Profit Assigning Work Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags