Non-overlapping Intervals

Q: Какова временная сложность алгоритма для непересекающихся интервалов?

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

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

+10

Интервал i длится от starts[i] до ends[i]. Верните минимальное количество интервалов, которые нужно удалить, чтобы никакие два из оставшихся не перекрывались. Два интервала, которые только соприкасаются, когда один заканчивается точно в той точке, где начинается другой, не перекрываются.

Функция

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: начало каждого интервала
endsinteger-array: конец каждого интервала с тем же индексом, что и его начало
Возвращаетinteger: минимальное количество интервалов, которые нужно удалить, чтобы остальные не пересекались

Ограничения

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Интервалы не отсортированы. Два интервала могут быть одинаковыми.

Примеры

Ввод: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Вывод: 2
Пояснение: В порядке начала интервалы такие: [1,4], [2,3], [3,6] и [5,7]. Оставьте [2,3] и [3,6], которые только соприкасаются, а остальные 2 удалите. Три интервала оставить нельзя: [1,4] пересекается с [2,3], а [3,6] пересекается с [5,7].

Ввод: starts = [0, 0, 0]ends = [5, 5, 5]
Вывод: 2
Пояснение: Все три интервала — [0,5], поэтому любые два пересекаются. Один остаётся, а 2 ты удаляешь.

Ввод: starts = [4, 1, 2]ends = [6, 2, 4]
Вывод: 0
Пояснение: [1,2], [2,4] и [4,6] соприкасаются концами и никогда не перекрываются, поэтому ничего удалять не нужно, и ответ — 0.

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

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

Решение

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

Сохраните или удалите каждый интервал

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

Идея

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

Каждый интервал может удвоить число ветвей, поэтому n интервалов дают до 2^n путей. Даже тридцать интервалов, которые не пересекаются, — это уже более миллиарда вызовов, а n может достигать 5000.

Алгоритм

Отсортируй интервалы по началу, сохранив соответствие каждого начала его концу.
Определи mostKept(i, last): максимальное количество интервалов, которые можно оставить начиная с позиции i, когда last — последний оставленный интервал (-1, если таких нет).
Если достигнут конец, верни 0. Иначе возьми mostKept(i+1, last), что означает удалить интервал i.
Если интервал i начинается в момент окончания last или позже, также попробуй 1 + mostKept(i+1, i) и оставь большее значение.
Верни n минус mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Самая длинная цепочка с помощью динамического программирования

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

Идея

Поиск снова и снова задаёт один и тот же вопрос: какова длина самой длинной цепочки, которая заканчивается этим интервалом? Ответь на него один раз для каждого интервала. Отсортируй интервалы по началу и пусть chain[i] обозначает максимальное число интервалов, которые можно оставить, если последним идёт интервал i.

Интервал, который может идти непосредственно перед i, заканчивается не позже, чем начинается starts[i], поэтому он начинается раньше и стоит раньше в отсортированном порядке. Отсюда получаем chain[i] = 1 + chain[j] для наилучшего подходящего j или 1, если подходящего интервала нет. В первом примере значения равны 1, 1, 2 и 2, поэтому ты оставляешь 2 интервала и удаляешь 2.

Вложенный цикл выполняет n(n-1)/2 проверок: около 12,5 миллиона при n = 5000.

Алгоритм

Отсортируй интервалы по началу, сохраняя каждый конец вместе с соответствующим началом.
Задай chain[i] = 1 для каждого интервала.
Для каждого i и каждого j < i, для которого ends[j] ≤ starts[i], задай chain[i] значение chain[j]+1, если оно больше.
Верни n минус наибольшее значение в chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Жадный алгоритм: оставляй интервал, который заканчивается раньше

Идея

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

В первом примере, если отсортировать интервалы по времени окончания, вы сохраняете [2,3], удаляете [1,4], сохраняете [3,6] и удаляете [5,7]. Если вместо этого сохранять самый короткий интервал, подход не сработает для [1,5], [4,7], [6,10]: [4,7] пересекается с обоими другими интервалами, поэтому придётся удалить два интервала, хотя достаточно удалить один.

Сортировка требует O(n log n), а проход — O(n).

Алгоритм

Отсортируй интервалы по конечным точкам, сохраняя каждую конечную точку вместе с её начальной точкой.
Оставь первый интервал: присвой lastEnd значение его конечной точки, а removed — значение 0.
Для каждого следующего интервала, если он начинается в момент lastEnd или позже, оставь его и присвой lastEnd значение его конечной точки.
В противном случае прибавь 1 к removed.
Верни removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

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

Считать соприкасающиеся интервалы пересекающимися. При условии start > lastEnd вместо start ≥ lastEnd цепочка [1,2], [2,4], [4,6] даёт 1 вместо 0.
Сортировать по началу и оставлять более ранний интервал при пересечении. Широкий интервал [0,100] вытеснит [1,2], [3,4] и [5,6]: получится три удаления вместо одного.
Сравнивать каждый интервал с соседним в отсортированном списке, а не с последним оставленным интервалом. В первом примере [3,6] нужно проверить относительно конца [2,3], а не удалённого [1,4], иначе ответ будет 3.
Сортировать starts и ends как два отдельных списка. Каждый конец должен оставаться при своём начале.
Возвращать количество оставленных интервалов вместо количества удалённых.

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

Какова временная сложность алгоритма для непересекающихся интервалов?

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

Можешь вместо этого отсортировать по времени начала?

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

Задача о непересекающихся интервалах — это то же самое, что задача выбора занятий?

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

def eraseOverlapIntervals(starts, ends):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

starts = [3, 1, 5, 2]
ends = [6, 4, 7, 3]

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

Non-overlapping Intervals

Функция

Ограничения

Примеры

Подсказки

Решение

Сохраните или удалите каждый интервал

Самая длинная цепочка с помощью динамического программирования

Жадный алгоритм: оставляй интервал, который заканчивается раньше

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

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

Похожие задачи