Задача: 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 {
    function maxProfitAssignment($difficulty, $profit, $worker) {
        $jobProfile = [[0, 0]];
        for ($i = 0; $i < count($difficulty); $i++) {
            $jobProfile[] = [$difficulty[$i], $profit[$i]];
        }
        usort($jobProfile, function($a, $b) {
            return $a[0] <=> $b[0];
        });
        
        for ($i = 1; $i < count($jobProfile); $i++) {
            $jobProfile[$i][1] = max($jobProfile[$i][1], $jobProfile[$i - 1][1]);
        }
        
        $netProfit = 0;
        foreach ($worker as $ability) {
            $l = 0;
            $r = count($jobProfile) - 1;
            $jobProfit = 0;
            while ($l <= $r) {
                $mid = intdiv($l + $r, 2);
                if ($jobProfile[$mid][0] <= $ability) {
                    $jobProfit = max($jobProfit, $jobProfile[$mid][1]);
                    $l = $mid + 1;
                } else {
                    $r = $mid - 1;
                }
            }
            $netProfit += $jobProfit;
        }
        return $netProfit;
    }
}

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