[Vlad Drakula]

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

[pva]

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

[ivank]

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

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

[pva]

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

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