Задачник по алгоритмам

Программа курса:

Задача 7: Пересечения списка интервалов

Напишите определение функции intervalIntersection(firstList, secondList), которая принимает два списка закрытых интервалов:

  • firstList — список закрытых интервалов, где каждый интервал представлен в виде [starti, endi].
  • secondList — список закрытых интервалов, где каждый интервал представлен в виде [startj, endj].

Каждый список интервалов:

  • Является попарно непересекающимся.
  • Отсортирован по возрастанию.

Функция должна вернуть список интервалов, которые являются пересечениями интервалов из firstList и secondList.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x, таких что a <= x <= b.

Пересечение двух закрытых интервалов — это множество чисел, которые либо пусты, либо представляют собой закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Примеры

Пример 1:

Ввод:
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]

Вывод:
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Объяснение:

  • Пересечение [0,2] и [1,5] равно [1,2].
  • Пересечение [5,10] и [1,5] равно [5,5].
  • Пересечение [5,10] и [8,12] равно [8,10].
  • Пересечение [13,23] и [15,24] равно [15,23].
  • Пересечение [24,25] и [15,24] равно [24,24].
  • Пересечение [24,25] и [25,26] равно [25,25].

Пример 2:

Ввод:
firstList = [[1,3],[5,9]]
secondList = []

Вывод:
[]

Объяснение:

  • Поскольку secondList пуст, пересечений быть не может.

Пример 3:

Ввод:
firstList = [[5,10]]
secondList = [[6,8]]

Вывод:
[[6,8]]

Объяснение:

  • Пересечение [5,10] и [6,8] равно [6,8].

0
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии