Задача: 826. Most Profit Assigning Work
Сложность: medium

У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.

Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям.

Пример:

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.

👨‍💻 Алгоритм:

1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.

2⃣Обновление максимальной прибыли для каждой сложности
Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли.

3⃣Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее.

😎 Решение:

class Solution:
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobProfile = [(0, 0)]
        for i in range(len(difficulty)):
            jobProfile.append((difficulty[i], profit[i]))
        jobProfile.sort()
        
        for i in range(1, len(jobProfile)):
            jobProfile[i] = (jobProfile[i][0], max(jobProfile[i][1], jobProfile[i-1][1]))
        
        netProfit = 0
        for ability in worker:
            l, r = 0, len(jobProfile) - 1
            jobProfit = 0
            while l <= r:
                mid = (l + r) // 2
                if jobProfile[mid][0] <= ability:
                    jobProfit = max(jobProfit, jobProfile[mid][1])
                    l = mid + 1
                else:
                    r = mid - 1
            netProfit += jobPro

Ставь 👍 и забирай 📚 Базу знаний