Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

1⃣Сортировка заданий:
Сначала мы сортируем задания по времени их окончания. Это позволит нам легко проверять, какие задания могут быть выбраны без пересечения с предыдущими выбранными заданиями.

2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.

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

😎 Решение:

function jobScheduling($startTime, $endTime, $profit) {
    $jobs = [];
    for ($i = 0; $i < count($startTime); $i++) {
        $jobs[] = [$endTime[$i], $startTime[$i], $profit[$i]];
    }
    usort($jobs, function($a, $b) {
        return $a[0] - $b[0];
    });

    $dp = [[0, 0]];

    foreach ($jobs as [$e, $s, $p]) {
        $i = 0;
        while ($i < count($dp) && $dp[$i][0] <= $s) $i++;
        $newProfit = $dp[$i - 1][1] + $p;
        if ($newProfit > $dp[count($dp) - 1][1]) {
            $dp[] = [$e, $newProfit];
        }
    }

    return $dp[count($dp) - 1][1];
}

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