Анонс #243. Перекрывающиеся интервалы

Анонс #243. Перекрывающиеся интервалы

UniLecs

Задача: Дан список интервалов. Необходимо удалить все интервалы, которые покрываются другим интервалом в списке. Функция должна вернуть количество оставшихся интервалов.

Справка: интервал [a, b) покрывается интервалом [c, d) тогда и только тогда, когда c <= a и b <= d.

Входные данные: список интервалов (i, j), где i < j. Размер списка от 1 до 10^5.

Вывод: кол-во интервалов после удаления перекрывающихся интервалов.

Примеры: 

  1. list = [ [1,4], [3,6], [2,8] ]
    Output: 2 (Интервал [3,6] покрывается интервалом [2,8], поэтому удаляем его).
  2. list = [ [1,4], [2,3] ]
    Output: 1

Report Page