Минимальное количество пар, которое необходимо выбрать, чтобы покрыть заданный диапазон

Дан массив arr[] , состоящий из N пар и положительного целого числа K , задача состоит в том, чтобы выбрать минимальное количество пар, чтобы оно покрывало весь диапазон [0, K] . Если невозможно покрыть диапазон [0, K] , то выведите -1 .

Примеры :

Input: arr[] = {{0, 3}, {2, 5}, {5, 6}, {6, 8}, {6, 10}}, K = 10
Output: 4
Explanation: One of the optimal ways is to select the ranges {{0, 3}, {2, 5}, {5, 6}, {6, 10}} which covers the entire range [0, 10].

Input: arr[] = {{0, 4}, {1, 5}, {5, 6}, {8, 10}}, N = 10
Output : -1

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

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

Эффективный подход. Приведенный выше подход можно оптимизировать, отсортировав массив в порядке возрастания на основе левого элемента, а для пар с равными левыми элементами отсортируйте элементы в порядке убывания их правого элемента. Теперь выберите пары оптимально.

Выполните следующие шаги, чтобы решить проблему:

• Отсортировать вектор пар arr[] по возрастанию левого элемента и, если левые элементы равны, то отсортировать массив по убыванию правого элемента пары.
• Проверьте, если arr[0][0] != 0 , затем напечатайте -1 .
• Инициализируйте переменную, скажем, R как arr[0][1] , которая хранит правую границу диапазона, и как 1 , которая хранит количество диапазонов, необходимых для охвата диапазона [0, K] .
• Выполните итерацию в диапазоне [0, N-1], используя переменную i , и выполните следующие шаги:
  • Если R == K , завершить цикл.
  • Инициализируйте переменную, скажем, maxr как R , которая хранит максимальную правую границу, где левая граница ≤ R.
  • Выполните итерацию в диапазоне [i+1, N-1], используя переменную j , и выполните следующие шаги:
    • Если arr[j][0] ≤ R , измените значение maxr как max(maxr, arr[j][1]) .
  • Измените значение i как j-1 и значение R как maxr и увеличьте значение ans на 1.
• Если R не равно K , то выведите -1 .
• В противном случае выведите значение ans .

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

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