Количество способов выбрать ровно K непересекающихся диапазонов из заданных N диапазонов

Опубликовано: 22 Сентября, 2022

Имея два массива L[] и R[] размера N и целое число K, задача состоит в том, чтобы найти количество способов выбрать точные K непересекающихся диапазонов, образованных путем взятия элементов с одним и тем же индексом из массива L[] и Р[].

Примеры :

Input: N = 7, K = 3, L[] = {1, 3, 4, 6, 1, 5, 8}, R[] = {7, 8, 5, 7, 3, 10, 9}
Output: 9
Explanation: 
The possible ways of selecting K ranges are: 

  1. Select ranges {1, 7}, {3, 8}, and {4, 5}
  2. Select ranges {1, 7}, {3, 8}, and {6, 7}
  3. Select ranges {1, 7}, {3, 8}, and {1, 3}
  4. Select ranges {1, 7}, {3, 8}, and {5, 10}
  5. Select ranges {1, 7}, {4, 5}, and {5, 10}
  6. Select ranges {1, 7}, {6, 7}, and {5, 10}
  7. Select ranges {3, 8}, {4, 5}, and {5, 10}
  8. Select ranges {3, 8}, {6, 7}, and {5, 10}
  9. Select ranges {3, 8}, {5, 10}, and {8, 9}

Input: N = 2, K = 2, L[] = {100, 200}, R[] ={ 201, 300}
Output: 0

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

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

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

  • Инициализируйте переменную, скажем, cnt для подсчета количества непересекающихся диапазонов для каждого текущего диапазона.
  • Инициализируйте вектор пар, скажем, предварительно обработанный , чтобы сохранить всю левую границу как {L[i], 1}, а правую границу как {R[i]+1, -1} диапазона.
  • Переберите диапазон [0, N] , используя переменную i , и выполните следующие шаги:
    • Вставьте пары {L[i], 1} и {R[i]+1, -1} в предварительно обработанный вектор.
  • Отсортируйте предварительно обработанный вектор в порядке неубывания.
  • Инициализируйте переменные, скажем, ans и cnt как 0 , чтобы сохранить ответ и сохранить сегмент, который пересекается с текущим диапазоном.
  • Переберите предварительно обработанный вектор с помощью переменной i и выполните следующие действия:
    • Если второй элемент пары равен 1 и cnt >= K-1, то увеличьте значение ans на cnt C K-1 и обновите cnt до cnt+1.
    • В противном случае обновите cnt как cnt+1.
  • Наконец, после выполнения вышеуказанных шагов, напечатайте ans .

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ