Сложность: 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⃣Для каждого задания мы можем либо взять его, либо не взять. Если мы берем задание, мы добавляем его прибыль к максимальной прибыли, полученной для заданий, которые заканчиваются до начала текущего задания. Для нахождения таких заданий используем двоичный поиск.
😎 Решение:
import bisect
def jobScheduling(startTime, endTime, profit):
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
dp = [(0, 0)]
for s, e, p in jobs:
i = bisect.bisect_right(dp, (s, float('inf')))
if dp[i-1][1] + p > dp[-1][1]:
dp.append((e, dp[i-1][1] + p))
return dp[-1][1]
Ставь 👍 и забирай 📚 Базу знаний