Job Sequencing Problem

+10

Тебе даны n заданий в виде двух массивов: за задание i ты получаешь profit[i], если завершаешь его не позднее времени deadline[i]. Каждое задание занимает одну единицу времени. Ты выполняешь по одному заданию за раз, начиная со времени 0, и можешь пропустить любое задание. Задание со сроком выполнения 2 можно выполнять с 0 до 1 или с 1 до 2.

Верни наибольшую общую прибыль, которую ты можешь получить.

Функция

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: время, к которому должна быть завершена каждая задача, от 1 до n
profitinteger-array: сколько приносит каждая задача; profit[i] относится к deadline[i]
Возвращаетinteger: наибольшая суммарная прибыль от заданий, которые могут быть завершены до своих сроков

Ограничения

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, где n — количество заданий
1 ≤ profit[i] ≤ 10⁵
Массивы не отсортированы. У нескольких заданий может быть одинаковый срок выполнения или прибыль.

Примеры

Ввод: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Вывод: 120
Пояснение: Помещается только одна из двух задач со сроком 1, поэтому выполни задачу стоимостью 50. Затем задача стоимостью 30 завершается к своему сроку 2, а задача стоимостью 40 — к своему сроку 3: 50 + 30 + 40 = 120.

Ввод: deadline = [1, 1, 1]profit = [5, 9, 7]
Вывод: 9
Пояснение: Все три задания должны завершиться к моменту 1, а до этого момента успевает выполниться только одно задание. Самое выгодное из них приносит 9.

Дополнительный вопрос

Что, если выполнение задания i занимает duration[i] единиц времени вместо одной? Даёт ли выполнение сначала самого прибыльного задания по-прежнему наилучший общий результат?

Решение

Ты выбираешь, какие задания оставить и когда их выполнять. Одно жадное правило решает обе задачи: бери задания от самых прибыльных к менее прибыльным и помещай каждое в самый поздний свободный слот до его срока включительно, пропуская задание, если свободных слотов нет. Система непересекающихся множеств находит такой слот, не проходя по уже занятым.

Жадный выбор по прибыли с поиском свободного слота

Идея

Разбейте время на слоты: слот t длится от t-1 до t, задача с дедлайном d может занимать слоты с 1 по d, а ни один дедлайн не превышает n. Сначала брать самую прибыльную задачу безопасно: если все слоты, которые она может занять, уже заняты, замена её на задачу в одном из этих слотов принесёт не меньше. Занимать самый поздний слот безопасно, потому что задачи с ранними дедлайнами могут использовать только ранние слоты.

Затраты связаны с поиском. Когда у каждой задачи дедлайн n, при обработке k-й задачи приходится пройти мимо k-1 занятых слотов: около n²/2, или 12,5 миллиона шагов при n = 5000.

Алгоритм

Отсортируй задания по прибыли от наибольшей к наименьшей, сохраняя срок выполнения каждого задания вместе с его прибылью.
Создай массив taken из n + 1 флагов, все они изначально равны false.
Для каждого задания перебирай t в обратном порядке, начиная со срока его выполнения и заканчивая 1, и остановись на первом свободном слоте.
Если такой слот найден, пометь его как занятый и добавь прибыль задания к total.
Верни total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Жадный алгоритм по прибыли с системой непересекающихся множеств свободных слотов

Идея

Сканирование снова и снова проходит по одним и тем же занятым слотам. Структура непересекающихся множеств для слотов от 0 до n пропускает их: parent[t] = t, пока слот t свободен, а при его бронировании устанавливается parent[t] = t-1, поэтому переход по указателям от крайнего срока приводит к последнему свободному слоту. Достигнув слота 0, мы понимаем, что свободных слотов больше не осталось. При укорочении путей указатель каждого пройденного слота направляется на два шага вперёд, поэтому последующие проходы становятся короче.

В третьем примере задания стоимостью 60 и 50 занимают слоты 2 и 1. Задание стоимостью 20 со сроком 2 проходит от 2 к 1, затем к 0 и пропускается.

Сортировка требует O(n log n), а при укорочении путей каждый поиск занимает в среднем O(log n), поэтому общая сложность остаётся O(n log n).

Алгоритм

Отсортируй задания по прибыли, от наибольшей к наименьшей, сохраняя соответствие каждого срока его прибыли.
Задай parent[t] = t для каждого слота t от 0 до n.
Для каждого задания начни со slot = deadline и следуй по parent, пока не будет выполнено parent[slot] == slot, по пути сокращая путь вдвое.
Если slot > 0, добавь прибыль задания и задай parent[slot] = slot-1; иначе пропусти задание.
Верни общую сумму.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

Ловушки и крайние случаи

Размещать задачу в самом раннем свободном слоте. В третьем примере задача стоимостью 60 заняла бы слот 1, и задача стоимостью 50 была бы потеряна: 80 вместо 110.
Брать задачи в порядке сроков. При сроках [1, 1] и прибылях [1, 100] дешёвая задача занимает единственный слот, и ты получаешь 1 вместо 100.
Задавать размер массива слотов n, а не n + 1. Тогда срок, равный n, приведёт к чтению за концом массива.
Сортировать только прибыли. Каждый срок должен перемещаться вместе со своей прибылью.
Реализовывать шаг поиска с помощью рекурсии. Цепочка из тысяч занятых слотов может привести к переполнению стека; используй цикл.

Частые вопросы3

Какова временная сложность задачи планирования заданий?

Для системы непересекающихся множеств время выполнения составляет O(n log n) — его определяет сортировка, а требуемая память — O(n). Поиск свободного места с обратным проходом от каждого срока выполнения занимает O(n²), если большинство сроков выполнения велики.

Почему жадный подход работает для планирования последовательности работ?

В оптимальном расписании содержится самая прибыльная работа. Если она пропущена и свободен слот до её дедлайна, её добавление принесёт больше; если все такие слоты заняты, замена одной из работ на неё принесёт не меньше. Этот аргумент повторяется для оставшихся работ.

Можно ли решить задачу планирования работ с помощью кучи?

Да. Отсортируй задачи по дедлайну и добавь прибыль от каждой задачи в минимальную кучу. Каждый раз, когда в куче оказывается больше задач, чем позволяет текущий дедлайн, извлеки наименьшую прибыль. В конце в куче останется оптимальный набор задач, а сумма их прибылей и будет ответом за O(n log n).

def jobSequencing(deadline, profit):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Ожидаемый вывод