Non-overlapping Intervals

Q: Какова временная сложность алгоритма Non-overlapping Intervals?

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

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

+10

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

Напиши функцию с именем eraseOverlapIntervals, которая возвращает наименьшее количество интервалов, которое нужно удалить.

Функция

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.

+17 скрытых тестов при отправке

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

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

Решение

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

Оставьте или удалите каждый интервал

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

Идея

Изменим формулировку задачи. Удалить минимальное количество интервалов означает оставить максимальное количество интервалов, которые не пересекаются, а ответ равен n минус это количество. Поэтому ищем наибольшее множество интервалов, которое можно оставить.

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

В первом примере отсортированные интервалы: [1,4], [2,3], [3,6], [5,7]. Если оставить [1,4], он блокирует [2,3] и [3,6], которые начинаются раньше 4, но остаётся место для [5,7]: оставлено 2 интервала. Если удалить [1,4], а [2,3] и затем [3,6] оставить, тоже останется 2 интервала. Ни одна ветвь не даёт 3, поэтому нужно удалить 4-2 = 2.

Каждый интервал может удвоить количество ветвей, поэтому n интервалов дают до 2^n путей. Уже тридцать непересекающихся интервалов означают более миллиарда вызовов, а в тестах может быть до 5000 интервалов. Рекурсия также достигает глубины n: на самых больших тестах это 5000 вызовов, что превышает стандартный лимит Python в 1 000.

Алгоритм

Отсортируй интервалы по началу, сохраняя соответствие каждого начала своему концу.
Определи 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] или раньше. Каждый такой интервал стоит раньше в отсортированном порядке: он начинается раньше, чем заканчивается, значит, начинается раньше starts[i]. Поэтому chain[i] = 1 + chain[j] для наилучшего более раннего j, где ends[j] ≤ starts[i], или 1, если подходящего интервала нет. Наибольшее значение в chain — это максимальное количество интервалов, которые можно оставить.

В первом примере после сортировки получаем [1,4], [2,3], [3,6], [5,7]; значения равны 1, 1, 2 и 2: за [2,3] может идти [3,6], а за [1,4] или [2,3] может идти [5,7]. Самая длинная цепочка состоит из 2 интервалов, поэтому нужно удалить 4-2 = 2.

Для каждого интервала проверяются все интервалы перед ним — всего n(n-1)/2 проверок. При n = 5000 это около 12.5 миллиона проверок: приемлемо для компилируемого языка, слишком медленно для более медленных языков на самых больших тестах и намного хуже приведённого ниже жадного алгоритма.

Алгоритм

Отсортируй интервалы по началу, сохранив соответствие каждого начала его концу.
Установи 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)

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

Идея

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

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

Первый пример после сортировки по концу выглядит так: [2,3], [1,4], [3,6], [5,7]. Оставьте [2,3], тогда lastEnd = 3. [1,4] начинается в момент 1, раньше 3: удалите его. [3,6] начинается в момент 3, не раньше 3: оставьте его, lastEnd = 6. [5,7] начинается в момент 5, раньше 6: удалите его. Удалены два интервала.

Другие критерии кажутся заманчивыми, но не подходят. При сортировке по началу остаётся [0,100], который охватывает [1,2], [3,4] и [5,6], и удаляются три интервала вместо одного. Выбор самого короткого интервала не работает для [1,5], [4,7], [6,10]: короткий [4,7] пересекается с обоими остальными, поэтому его выбор приводит к двум удалениям, хотя достаточно одного. Именно конец оставляет больше всего места для всех последующих интервалов.

Сортировка требует O(n log n), а проход по списку — O(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] будет удалён [2,4], который начинается ровно там, где заканчивается [1,2], и ответ получится равным 1 вместо 0.
Сортировать по началу и всегда оставлять более ранний интервал при пересечении. Широкий интервал [0,100] вытеснит [1,2], [3,4] и [5,6]. Если сортируете по началу, оставляйте тот из двух пересекающихся интервалов, который заканчивается раньше.
Сравнивать каждый интервал с соседним в отсортированном списке, а не с последним оставленным интервалом. После удаления [1,4] следующий интервал нужно сравнить с концом [2,3], а не с 4.
Сортировать starts и ends как два отдельных списка. Каждое окончание должно оставаться связанным со своим началом, иначе вы сравните начало одного интервала с окончанием другого.
Возвращать количество оставленных интервалов. В задаче спрашивается количество удалённых интервалов, то есть n минус это число.

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

Какова временная сложность алгоритма Non-overlapping Intervals?

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

Почему сортировка по времени окончания дает наименьшее количество удалений?

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

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

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

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

Non-overlapping Intervals

Функция

Ограничения

Примеры

Подсказки

Решение

Оставьте или удалите каждый интервал

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

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

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

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

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