Activity Selection Problem

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

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

ЛегкоЖадные алгоритмы Сортировка

+10

Задание i длится с момента start[i] до момента finish[i]. Один человек выполняет только одно задание за раз, и следующее задание должно начинаться строго после завершения предыдущего: задание, начинающееся ровно в момент завершения другого, не может идти следом за ним.

Верните максимальное количество заданий, которые может выполнить один человек.

Функция

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: время начала каждого действия
finishinteger-array: время завершения каждого действия; finish[i] соответствует start[i]
Возвращаетinteger: наибольшее количество занятий, которые один человек может выполнять одно за другим

Ограничения

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
Действие может начинаться и заканчиваться одновременно. Массивы не отсортированы.

Примеры

Ввод: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
Вывод: 4
Пояснение: Выполнение с 10 по 13, с 14 по 19, с 21 по 22 и с 25 по 30 даёт 4. Пять невозможно: с 10 по 13 пересекается с 12 по 16, а с 21 по 22 — с 20 по 24.

Ввод: start = [1, 5, 9]finish = [5, 9, 12]
Вывод: 2
Пояснение: Задание с 5 до 9 начинается точно в тот момент, когда заканчивается первое, поэтому оно не может следовать за ним. Если выполнить задание с 1 до 5, а затем с 9 до 12, всё получится, поэтому ответ — 2.

Ввод: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
Вывод: 3
Пояснение: Действие от 0 до 100 пересекается со всеми остальными. Если его пропустить, 2–4, 5–7 и 8–10 идут одно за другим: 3.

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

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

Решение

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

Снова и снова выбирайте тот, кто заканчивает раньше всех

Верно, но не успевает на самых больших тестах

Идея

Занятие, которое заканчивается раньше всех, как минимум не хуже любого другого варианта для первого выбора. Оно освобождает вас не позже, поэтому всё, что могло следовать за другим первым выбором, может следовать и за ним, а замена на него сохраняет количество. После этого выбора задача повторяется для занятий, которые начинаются после его окончания.

В первом примере вы выбираете 10–13, затем 14–19, затем 21–22, затем 25–30: всего четыре.

При каждом выборе просматриваются все n занятий, поэтому затраты равны n, умноженному на ответ. Если все 5000 занятий помещаются одно за другим, это 25 миллионов проверок.

Алгоритм

Установи count = 0 и lastFinish = -1 ниже каждого начала.
Просмотри все активности и найди ту, у которой start[i] > lastFinish и которая заканчивается раньше всех.
Если такой нет, верни count.
Иначе увеличь count на 1, присвой lastFinish время окончания этой активности и просканируй снова.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

Отсортируйте по времени завершения и выбирайте жадно

Идея

Один раз отсортируй занятия по времени окончания, и ты встретишь их в том порядке, в котором их искали приведённые выше проходы. Пройди по отсортированному списку, отслеживая lastFinish — время окончания последнего выбранного тобой занятия. Занятие, для которого start[i] > lastFinish, заканчивается раньше всех тех, что ещё подходят, поэтому выбери его. Любое другое пересекается с последним выбранным тобой занятием, так что пропустить его ничего не стоит.

После сортировки первый пример выглядит так: с 10 до 13, с 12 до 16, с 14 до 19, с 21 до 22, с 20 до 24, с 25 до 30. Ты выбираешь первое, третье, четвёртое и шестое: 12 не позже 13, а 20 не позже 22.

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

Алгоритм

Отсортируй занятия по finish, перемещая каждое время начала вместе с временем окончания.
Установи count = 0 и lastFinish = -1.
Для каждого занятия в этом порядке, если start[i] > lastFinish, прибавь 1 к count и установи lastFinish = finish[i].
Верни count.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

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

Сортировка по времени начала. В третьем примере отрезок от 0 до 100 начинается первым и блокирует остальные три.
Выбор сначала самой короткой активности. При активностях от 1 до 5, от 5 до 6 и от 6 до 10 самой короткой является активность от 5 до 6, которая конфликтует с обеими другими; активности от 1 до 5 и от 6 до 10 дают результат 2.
Сравнение с ≥ вместо >. Во втором примере это возвращает 3 вместо 2.
Отдельная сортировка finish. Каждое время начала должно перемещаться вместе со своим временем окончания, иначе времена начала будут сопоставлены не с теми активностями.
Установка начального значения lastFinish в 0. Тогда единственная активность от 0 до 1 будет пропущена, потому что 0 > 0 — это false.

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

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

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

Что такое задача о N встречах в одной комнате?

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

Является ли задача выбора занятий задачей динамического программирования?

Это возможно, но необязательно. Таблица по занятиям, отсортированным по времени окончания, в которой хранится максимальное количество занятий, заканчивающихся каждым из них, даёт ответ за O(n²). Жадный выбор всегда безопасен, поэтому достаточно одного прохода. Таблица становится подходящим инструментом, когда занятия имеют значения и нужно максимизировать их сумму.

def maxActivities(start, finish):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

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