pva
15-04-2007, 17:02
Очередная безумная задачка: (объясняю по пунктам)
1. есть N обработчиков событий (пусть N=3).
2. На них поступают события - занятость обработчиком с момента времени a1 до момента a2.
3. Последовательность событий известна заранее (и может незначительно меняться до момента обработки).
4. Возможны простои (то есть не обязательно должно упаковываться вплотную)
5. Не важно, кто обработает
но надо как можно плотнее упаковать события ("дефрагментировать" свободное место)
допустимо рекурсивное решение задачи (было оптимальное решение, добавили, изменили или удалили одно событие),
допустимо неполное решение (дефрагментация на 95%)
пример заполнения:
1: xxx bbbb 1: xxx
2: xxxaaa xxxx -> 2: xxx xxxx
3: xxx xxx 3: xxxaaa bbbbxxx
в голову ничего не идёт :-(
пойдёт любая идея, ссылка или алгоритм
смотрел:
1. задачу в 8 ферзях - не то
2. задачу о тетрисе - решается полным перебором (а у меня N примерно 500 и примерно по 10 событий на обработчик, т.е. итого 5000 блоков)
Если поможет:
когда ставят задания как попало, часто возникает ситуация, когда нет свободного обработчика из-за фрагментации (а на самом деле можно всё растолкать и воткнуть задание). Работу выполняют люди с ОЧЕНЬ сильным человеческим фактором, вот и хочется и им помочь и предприятию и себе (достали звонками уже).
Ну и...
за полезные сообщения могу разработками поделиться ;-)
1. есть N обработчиков событий (пусть N=3).
2. На них поступают события - занятость обработчиком с момента времени a1 до момента a2.
3. Последовательность событий известна заранее (и может незначительно меняться до момента обработки).
4. Возможны простои (то есть не обязательно должно упаковываться вплотную)
5. Не важно, кто обработает
но надо как можно плотнее упаковать события ("дефрагментировать" свободное место)
допустимо рекурсивное решение задачи (было оптимальное решение, добавили, изменили или удалили одно событие),
допустимо неполное решение (дефрагментация на 95%)
пример заполнения:
1: xxx bbbb 1: xxx
2: xxxaaa xxxx -> 2: xxx xxxx
3: xxx xxx 3: xxxaaa bbbbxxx
в голову ничего не идёт :-(
пойдёт любая идея, ссылка или алгоритм
смотрел:
1. задачу в 8 ферзях - не то
2. задачу о тетрисе - решается полным перебором (а у меня N примерно 500 и примерно по 10 событий на обработчик, т.е. итого 5000 блоков)
Если поможет:
когда ставят задания как попало, часто возникает ситуация, когда нет свободного обработчика из-за фрагментации (а на самом деле можно всё растолкать и воткнуть задание). Работу выполняют люди с ОЧЕНЬ сильным человеческим фактором, вот и хочется и им помочь и предприятию и себе (достали звонками уже).
Ну и...
за полезные сообщения могу разработками поделиться ;-)