Минимум разбрызгивателей, необходимых для полива растений

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

Дан массив arr[] , состоящий из N целых чисел, где i -й элемент представляет диапазон разбрызгивателя, т.е. [i-arr[i], i+arr[i]] , который он может поливать, задача состоит в том, чтобы найти минимальное число разбрызгивателя, который должен быть включен для полива каждого растения в галерее. Если невозможно полить каждое растение, выведите -1.
Примечание. Если arr[i] = -1 , спринклер не может быть включен.

Примеры:

Input: arr[ ] = {-1, 2, 2, -1, 0, 0}
Output: 2
Explanation: 
One of the possible way is:

  • Turn on the sprinkler at index 2, it can water the plants in the range [0, 4].
  • Turn on the sprinkler at index 5, it can water the plants in the range [5, 5].

Therefore, turning two sprinklers on can water all the plants. Also, it is the minimum possible count of sprinklers to be turned on.

Input: arr[ ] = {2, 3, 4, -1, 2, 0, 0, -1, 0}
Output: -1

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

  • Инициализируйте вектор <pair<int, int>>, скажем, V , чтобы сохранить диапазон каждого разбрызгивателя в виде пары.
  • Обходим массив arr[] и, если arr[i] не равен -1 , вставляем пару (i-arr[i], i+arr[i]) в вектор V .
  • Отсортируйте вектор пар в порядке возрастания по первому элементу.
  • Инициализируйте 2 переменные, скажем, res и maxRight , чтобы сохранить минимальное количество разбрызгивателей, которые должны быть включены, и сохранить крайнюю правую границу массива.
  • Инициализируйте переменную, скажем, i как 0 , чтобы перебрать V.
  • Повторяйте до тех пор, пока maxRight не станет меньше N , и выполните следующие шаги:
    • Если i равно V.size() или V[i].first больше, чем maxRight, тогда выведите -1 и вернитесь.
    • Сохраните правую границу текущего разбрызгивателя в переменной, скажем, currMax .
    • Теперь повторяйте до тех пор, пока i+1 не станет меньше, чем V.size(), а V[i+1].first не будет меньше или равен maxRight, затем в каждой итерации увеличивайте i на 1 и обновляйте currMax как currMax = max(currMax, V[ я]. второй).
    • Если currMax меньше, чем maxRight , выведите -1 и верните значение.
    • Обновите maxRight как maxRight = currMax+1 , затем увеличьте res и i на 1 .
  • Наконец, после выполнения вышеуказанного шага, напечатайте res в качестве ответа.

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

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

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