|*теория*| дефрагментируем события
 

Очередная безумная задачка: (объясняю по пунктам)
1. есть N обработчиков событий (пусть N=3).
2. На них поступают события - занятость обработчиком с момента времени a1 до момента a2.
3. Последовательность событий известна заранее (и может незначительно меняться до момента обработки).
4. Возможны простои (то есть не обязательно должно упаковываться вплотную)
5. Не важно, кто обработает
но надо как можно плотнее упаковать события ("дефрагментировать" свободное место)
допустимо рекурсивное решение задачи (было оптимальное решение, добавили, изменили или удалили одно событие),
допустимо неполное решение (дефрагментация на 95%)
пример заполнения:
в голову ничего не идёт :-(
пойдёт любая идея, ссылка или алгоритм

смотрел:
1. задачу в 8 ферзях - не то
2. задачу о тетрисе - решается полным перебором (а у меня N примерно 500 и примерно по 10 событий на обработчик, т.е. итого 5000 блоков)

Если поможет:
когда ставят задания как попало, часто возникает ситуация, когда нет свободного обработчика из-за фрагментации (а на самом деле можно всё растолкать и воткнуть задание). Работу выполняют люди с ОЧЕНЬ сильным человеческим фактором, вот и хочется и им помочь и предприятию и себе (достали звонками уже).
Ну и...
за полезные сообщения могу разработками поделиться ;-)

pva
как то не очень нонятно объяснили...
может попытаетесь по понятнее объяснить?

Нашёл похожую задачу - укладку прямоугольников на бесконечной полосе. Отличается тем, что у меня нельзя двигать вдоль полосы. Попробую перефразировать в этом духе:
Есть бесконечная полоса ширины N (целое). Есть несколько прямоугольников ширины 1, заданной длины L[i] (вещественное) и положения вдоль полосы x[i] (вещественное). Нужно расположить их так (меняя только y[i], целое), так чтобы они все поместились на полосе. Если все поместить невозможно, то разместить как можно большее их число.

pva
У меня кажется есть решение (на основе т.н. динамического программирования). Только хочу уточнить некоторые условия, прежде чем идею попытаюсь развить. Я правильно понял, что (перефразируя начальны пост):
1. есть поток потяжённых во времени задач (задающихся начальной и конечной точкой во времени)
2. задачи могу по времени перекрываться
3. Для каждой задачи нужно назвать обработчик, на который она пойдёт, или просто сбросить её (не обрабатывать вообще)
4. После того как обработчик получил задачу он освободится (т.е. на него может быть назначена другая) только после того, как текущая полностью выполнится.
5. Требуется выполнить как можно большее число задач.
?

Так же интересуют ограничения по памяти и времени на всё решение задачи.

Совершенно верно! По времени: чтобы на p4-1600 обрабатывалась не больше 5 сек, память не больше 50 МБ (под данные). Ограничения могут быть только вроде "непередвигаемых" заданий, то есть если сказали на обработчике №99, значит только на нём.

А можно формулировку критерия оптимизации? я что-то никак не могу составить.