Минимальное время, необходимое для планирования K процессов

Даны положительное целое число K и массив arr[] , состоящий из N положительных целых чисел, такой, что arr[i] — это количество процессов, которые i ^-й процессор может запланировать за 1 секунду . Задача состоит в том, чтобы минимизировать общее время, необходимое для планирования K процессов таким образом, чтобы после планирования i ^-м процессором arr[i] сократилось до floor(arr[i]/2).

Примеры:

Input: N = 5, arr[] = {3, 1, 7, 2, 4}, K = 15
Output: 4
Explanation:
The order of scheduled process are as follows:

1. The 3^rd process is scheduled first. The array arr[] modifies to {3, 1, 3, 2, 4}, as arr[2] = floor(arr[2] / 2) = floor(7 / 2) = 3.
2. The 5^th process is scheduled next. The array arr[] modifies to {3, 1, 3, 2, 2}.
3. The 1^st process is scheduled next. The array arr[] modifies to {1, 1, 3, 2, 2}.
4. The 2^nd process is scheduled next. The array arr[] modifies to {3, 0, 3, 2, 4}.

The total processes scheduled by all the process = 7 + 4 + 3 + 1 = 15(= K) and the total time required is 4 seconds.

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

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

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

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

• Инициализировать вспомогательный массив tmp[] размером с максимальный элемент, присутствующий в данном массиве.
• Инициализируйте переменную, скажем, count , чтобы сохранить минимальное время для планирования всех процессов соответственно.
• Пройдите заданный массив tmp[] с конца и выполните следующие шаги:
  • Если текущий элемент в tmp[] больше 0 и i * tmp[i] меньше K .
    • Уменьшите значение K на значение i * tmp[i] .
    • Увеличьте tmp[i/2] на tmp[i] , так как мощность процессора уменьшится вдвое.
    • Увеличьте значение count на значение tmp[i] .
    • Если значение K уже меньше или равно 0 , то в качестве результата выведите значение count .
  • Если текущий элемент в массиве tmp[] не меньше 0 , а значение i * tmp[i] не меньше K , выполните следующие шаги:
    • Если K делится на текущий индекс, то увеличьте значение count на K/i .
    • В противном случае увеличьте значение count на K/i +1 .
• После выполнения вышеуказанных шагов выведите -1 , если невозможно запланировать все процессы. В противном случае выведите количество как минимальное требуемое время.

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

Временная сложность: O(M), где M — максимальный элемент в массиве .
Вспомогательное пространство: O(M)

Альтернативный подход (с использованием STL): данная проблема может быть решена с использованием жадного подхода с помощью max-heap. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте приоритетную очередь, скажем, PQ, и вставьте все элементы заданного массива в PQ.
• Инициализируйте переменную, скажем, как 0, чтобы сохранить результирующий максимальный полученный алмаз.
• Итерировать цикл до тех пор, пока приоритетная очередь PQ не станет пустой и значение K > 0:
  • Извлеките верхний элемент приоритетной очереди и добавьте извлеченный элемент в переменную ans.
  • Разделите извлеченный элемент на 2 и вставьте его в приоритетную очередь PQ.
  • Уменьшите значение K на 1.
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans.

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

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

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