Минимальное время для выполнения не менее K задач, когда все отдыхают после каждой задачи

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

Дан массив arr[] размера N , представляющий время, затраченное человеком на выполнение задачи. Кроме того, массив restTime[] , который обозначает количество времени, в течение которого человек отдыхает после завершения задачи. Каждый человек независим от других, т.е. он может одновременно работать над разными задачами. Для заданного целого числа K задача состоит в том, чтобы найти, по крайней мере, сколько времени потребуется для выполнения всех K задач всеми людьми.

Примеры:

Input: arr[] = {1, 2, 4}, restTime[] = {1, 2, 2}, K = 5
Output: 5
Explanation: At t = 1, tasks task done = [1, 0, 0], Total task = 1
At t = 2, No of tasks completed = [1, 1, 0],  
Total task = 1 + 1 = 2. Because 1st person was taking rest
At t = 3, No of tasks completed = [2, 1, 0],  
Total task = 2 + 1 = 3, Because 2nd person was taking rest
At t = 4, No of tasks completed = [2, 1, 1],  
Total task = 2 + 1 + 1 = 4, Because 1st and 2nd person was taking rest
At t = 5, No of tasks completed = [3, 1, 1]. 
Total task = 3 + 1 + 1 = 5. Minimum time taken = 5.

Input: arr[] = {1, 2, 4, 7, 8}, restTime[] = {4, 1, 2, 3, 1}, TotalTask = 2
Output: 2

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

The minimum time taken can be 1 and maximum time required can be very large. If in time x all the K tasks can be completed, then it is also possible that they can be completed in less than x time. Use this concept to apply binary search on the time required. 

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

  • Создайте переменную st = 1, представляющую начальную точку временного диапазона, и end = INT_MAX, конечную точку.
  • Используйте бинарный поиск в диапазоне от st до end :
    • Вычислить середину = ст + (конец - ст)/2
    • Проверьте, можно ли выполнить K задач за среднее время:
      • Если это может быть завершено, установите end = mid-1.
      • В противном случае установите st = mid+1.
  • Верните st в конце, так как это будет минимальное требуемое время.

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

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

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