Непересекающиеся интервалы

Средняя

medium , array , dynamic programming

26 January 2024

Описание задачи #

Дан массив интервалов intervals, где intervals[i] = [start_i, end_i]. Напишите функцию, которая возвращает минимальное количество интервалов, которое вам нужно удалить, чтобы остальные интервалы не пересекались.

Ограничения #

Длина массива находится в диапазоне от 1 до 10⁵
Каждый элемент массива также является массивом из двух элементов
Значения границ интервалов находятся в диапазоне от -5 * 10⁴ до 5 * 10⁴
Нижняя граница интервала всегда меньше верхней

Примеры #

Входные данные: [[1,2],[2,3],[3,4],[1,3]]

Ответ: 1

Интервал [1,3] можно удалить, а остальные не перекрываются.
Входные данные: [[1,2],[1,2],[1,2]]

Ответ: 2

Нужно удалить два интервала [1,2], чтобы остался один не пересекающийся.
Входные данные: [[1,2],[2,3]]

Ответ: 0

Не нужно удалять какие-либо интервалы, поскольку они уже не перекрываются.

Решение #

Рассмотрим два интервала с самым ранним временем окончания. Допустим, более раннее время окончания — x, а более позднее — y, то есть х < у.

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

Мы выбираем либо x, либо y. Назовем наш выбор k.
Чтобы избежать пересечения, время начала следующего интервала, который мы выбираем, должно быть больше или равно k.
Мы хотим максимизировать интервалы, которые мы используем (без пересечения), поэтому мы хотим максимизировать выбор для следующего интервала.
Поскольку время начала следующего интервала должно быть больше или равно k, большее значение k никогда не сможет дать нам больше выбора, чем меньшее значение k.
Таким образом, мы должны попытаться минимизировать k. Следовательно, нам всегда следует жадно выбирать x, поскольку x < y.

В общем, k равно времени окончания самого последнего сохраненного нами интервала.

Решение задачи мы начинаем с сортировки интервалов по времени окончания, чтобы мы могли обрабатывать интервалы по порядку.

Поскольку мы отсортировали интервалы по времени окончания, y должно быть больше k. Это дает нам два возможных варианта:

Вариант 1, x >= k: мы можем смело использовать этот интервал, поскольку он не приведет к пересечению.
Вариант 2, x < k: использование этого интервала приведет к пересечению. Как мы установили ранее, нам всегда следует брать интервалы с более ранним временем окончания. Поскольку y > k, мы должны удалить текущий интервал.

Реализация #

package main

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})

	res := 0
	k := intervals[0][1]

	for idx := 1; idx < len(intervals); idx++ {
		end := intervals[idx][1]
		start := intervals[idx][0]

		if start >= k {
			k = end
		} else {
			res++
		}
	}

	return res
}

export const eraseOverlapIntervals = (intervals: number[][]): number => {
    intervals.sort((a, b) => {
        return a[1] - b[1]
    })

    let res = 0
    let k = intervals[0][1]

    for (let i = 1; i < intervals.length; i++) {
        const end = intervals[i][1]
        const start = intervals[i][0]

        if (start >= k) {
            k = end
        } else {
            res++
        }
    }

    return res
}

Оценка сложности #

По времени

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

Поэтому итоговая сложность по времени равна O(n⋅log_n).

По памяти

Мы не создаем переменных, зависящих от длины входных данных, однако для сортировки также требуется выделение памяти. В разных языках используются разные алгоритмы, поэтому сложность по памяти будет варьироваться от O(log_n) до O(n).

Оригинал задачи на Leetcode

Algorithmics