Минимальное количество интервалов для покрытия целевого интервала

Учитывая массив A[] , состоящий из N интервалов, и целевой интервал X , задача состоит в том, чтобы найти минимальное количество интервалов из данного массива A[] , чтобы они полностью покрывали целевой интервал. Если такого интервала не существует, выведите «-1» .

Примеры:

Input: A[] = {{1, 3}, {2, 4}, {2, 10}, {2, 3}, {1, 1}}, X = {1, 10}
Output: 2
Explanation:
From the given 5 intervals, {1, 3} and {3, 10} can be selected. Therefore, the points in the range [1, 3] are covered by the interval {1, 3} and the points in the range [4, 10] are covered by the interval {2, 10}.

Input: A[] = {{2, 6}, {7, 9}, {3, 5}, {6, 10}}, X = {1, 4}
Output: -1
Explanation: There exist no set of intervals in the given array A such that they cover the entire target interval.

Подход: Данную проблему можно решить с помощью жадного подхода. Можно заметить, что наиболее оптимальным выбором интервала от точки p в целевом диапазоне является интервал (u, v) такой, что u <= p и v является максимально возможным. Используя это наблюдение, выполните следующие шаги, чтобы решить данную проблему:

• Отсортируйте заданный массив A[] в порядке возрастания начальных точек интервалов.
• Создайте переменную start и инициализируйте ее начальной точкой целевого интервала X . Он сохраняет начальную точку текущего выбранного интервала. Точно так же конец переменной хранит конечную точку текущей переменной. Инициализируйте его start-1 .
• Создайте переменную cnt , в которой хранится количество выбранных интервалов.
• Перебрать заданный массив A[] с помощью переменной i .
• Если начальная точка i ^-го интервала <= start, обновите значение end на max(end, конечная точка i ^-го интервала), в противном случае установите start = end и увеличьте значение cnt на 1 .
• Если начальная точка i ^-го интервала > end или значение end уже больше, чем конечная точка целевого интервала, цикл прерывается.
• Вернуть -1 , если значение end < конечной точки целевого интервала, иначе вернуть значение cnt .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(1)