Сложность: 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:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
ans = 0
k = float('-inf')
for x, y in intervals:
if x >= k:
k = y
else:
ans += 1
return ans
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
ans = 0
k = float('-inf')
for x, y in intervals:
if x >= k:
k = y
else:
ans += 1
return ans
Ставь 👍 и забирай 📚 Базу знаний