Задача: 435. Non-overlapping Intervals
Сложность: medium

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

👨‍💻 Алгоритм:

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    function eraseOverlapIntervals($intervals) {
        usort($intervals, function($a, $b) {
            return $a[1] - $b[1];
        });
        $ans = 0;
        $k = -INF;
        
        foreach ($intervals as $interval) {
            list($x, $y) = $interval;
            if ($x >= $k) {
                $k = $y;
            } else {
                $ans++;
            }
        }
        
        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний