В случае одного работника фактическое общее требуемое время совпадает с суммой всех времен выполнения задания.
jobs = [ 2, 4, 6, etc... ]
time_required = SUM( jobs )
В случае двух работников, тогда , учитывая Для указания c порядка заданий общее требуемое время можно определить, сначала назначив требуемое время каждой задаче тому, с кем у него связана текущая минимальная сумма, а затем получив наибольшую сумму, связанную с каждым работником:
define type worker = vector<time_t>
define type workers = min_priority_queue<worker> using worker.sum() # so the current worker.sum() (the sum of `time_t` values in `vector<time_t>`) is the priority-queue key.
define type task = int
jobs = [ 2, 4, 6, etc... ]
# Use two workers:
workers.add( new worker )
workers.add( new worker )
# Iterate once through each job:
foreach( task t in jobs ) {
minWorker = workers.getMinWorker() # priority queue "find-min" operation
minWorker.add( t )
}
# Determine which worker will work the longest time:
time_required = workers.getMaxWorker().sum() # priority queue "find-max" operation
Поскольку это реальное решение, то time_required является точечным образцом, который существует между верхней и нижней границами - что не совсем то, что вам нужно, а потому, что его можно вычислить через O(n) время это хорошая отправная точка.
Приведенный выше алгоритм можно затем обобщить на любое количество рабочих, просто добавив их в очередь приоритетов - так как операция find-min очередей на основе кучи имеет вид O(1) Я полагаю, что этот алгоритм выполняется за O(n) время, где n - это число рабочих мест, не зависящее от количества рабочих. (Я могу ошибаться насчет точной сложности времени выполнения).
Что касается вычисления границ за меньшее время, чем O(n!) время ... это сложно (по крайней мере, для меня, так как прошло несколько лет с тех пор, как я в последний раз взломанный моя копия CLRS ).
Минимальная нижняя граница для x рабочих для любого порядка заданий является просто наибольшим единственным значением в набор заданий.
Максимальная верхняя граница для x работников для любого порядка работ может быть суммой самых больших 100 * (1/x) % заданий (так для 2 работников это сумма самых больших 50% рабочих мест, для 3 работников это сумма самых больших 33% рабочих мест, для 4 работников это 25% и т. д. c). Это потребует от вас сначала отсортировать набор (принимая O(n log n) при использовании быстрой сортировки).
jobs = [ 2, 4, 6, etc... ]
worker_count = 2
jobs.sortDescending() # O(n log n)
# if there's 50 jobs and 2 workers, then take the first 25 jobs and sum them...
# ...that's an upper_bound for the time required to complete all tasks by 2 workers, as it assumes that 1 unlucky worker will get all of the longest tasks
upper_bound = jobs.take( jobs.count / worker_count ).sum()