Какой подойдет алгорим для распеределения задач по времени?

Question

[Андрей]

Ни как не могу придумать алгоритм распеределение задач по времени.

Дано: N задач у которых есть интервал (например с 15:00 до 19:00) в которое она (задача) должна выполнится. Нужно их равномерно распределить по времени.
Например: 1k задач надо выполнить с 12:00 до 12:15 а также 100k с 11:00 до 19:00 и еще 500 задач с 18:45 до 18:55
Задач примерно 200 мллионов.

Проблема в том что надо равномерно (на сколько возможно) распеределить задачи, ведь если просто 100к размазать с 11:00 до 19:00 то 18:45 до 18:55 будет всплек из за тех 500 задач.

Answer 1

[xmoonlight]

Никакой.
Только сменой условия.
Можно или уменьшать интервалы (поглощающие пересекающиеся интервалы) или увеличивать (на длительность пересекающихся -> добавлять).

Comments

[Андрей]

Задача как раз и сосотоит в поиске алгоритма который максимально сгладит всплески (пересечения) если это возможно.

[xmoonlight]

Андрей: временной интервал каждого поглощающего множества (конец-начало) делим на кол-во задач всех поглощённых множеств.

[alexxandr]

Андрей: имитацию отжига делай, там сразу покажет

Answer 2

[alexxandr]

раскидай 100к с 11:00 до 18:45

Comments

[Андрей]

Проблема как раз что бы это определять программно.

[alexxandr]

т.е. ситуация такая:
есть N задач, для каждой есть интервал выполнения Tm = [tk..tj]
Есть временной отрезок T = [t0..tn], включающий в себя все Tm
Тогда n(t) - функция, описывающая число задач, выполняющихся в некоторый момент времени t.
Далее ищем локальные максимумы n(t) и действуем сообразно с этим (смещаем некоторое число задача во времени вперед/назад)

[alexxandr]

Интеграл от n(t) по dt от t0 до tn будет точно равен N