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

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

Учитывая массив task[] размера N , обозначающий объем работы, который необходимо выполнить для каждой задачи, проблема состоит в том, чтобы найти минимальный объем работы, который необходимо выполнить в каждый день, чтобы все задачи можно было выполнить не более чем за D дней.

Примечание: В один день работа может выполняться только по одному заданию.

Примеры:

Input: task[] = [3, 4, 7, 15],  D = 10
Output: 4
Explanation:  Here minimum work to be done is 4.
On 1st day, task[0] = 3 < 4 so this task can only be completed. Because work can be done for only one task on one day.
For task[1] = 4 the task can be completed in 1 day.
Task[2] = 7. Now 4 amount of work can be done in 1 day so to complete this task 2 days are required.
Task[3] = 15, 4 additional days are required.
Total number of days required = 1 + 1 + 2 + 4 = 8 days < D. 
So 4 value would be the minimum value.

Input: task[] = [30, 20, 22, 4, 21], D = 6
Output: 22

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

The minimum work that can be done each day is 1 and the maximum work that can be done is the maximum of the tasks array. 
Search on this range and if the mid-value satisfies the condition then move to 1st half of the range else to the second half. 

Выполните шаги, упомянутые для реализации подхода:

  • Создайте переменную left = 1 , представляющую начальную точку диапазона, переменную right = INT_MIN .
  • Запустите цикл от индекса = 0 до индекса = N — 1 и обновите право = макс (право, задача [индекс]).
  • Создайте переменную per_day_task = 0 для хранения ответа.
  • Запустите условие while с левой <= правой
    • создайте переменную mid = left + (right – left)/2.
    • если все задачи можно выполнить в течение D дней, выполняя средний объем работы в каждый день, обновите per_day_task = mid и сделайте правильно = mid — 1.
    • иначе справа = середина + 1.
  • Выведите per_day_task как минимальное количество задач, выполняемых каждый день, чтобы выполнить все задачи.

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


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

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