Алгоритм планирования событий

Question

У меня есть список событий, каждый из которых имеет продолжительность. Я ищу, чтобы написать алгоритм для планирования этих событий в течение дня. С 9 утра до 12 вечера, а затем с 1 вечера до не более 4 вечера и не позднее 5 вечера.

Я не уверен, что будет хорошим подходом к решению этого вопроса. Так как может быть несколько возможных решений, моя первая мысль - проверить случайные комбинации для правильности.

Хотелось бы узнать, существует ли более детерминированный способ решения этого вопроса. Благодаря ;)

РЕДАКТИРОВАТЬ

@svs Время для событий в течение нескольких минут и события не должны перекрывать друг друга. Также нет необходимости в паузах между событиями, кроме обеденного перерыва с 12 вечера до 1 вечера.

Answer 1

Хорошо. Так как у вас в основном есть два равных промежутка времени, вы можете по существу запланировать их все в последовательности, независимо от порядка, и, предполагая, что есть решение, ищите, как вы можете их вытащить. Начните с ведрами A и B.

Поместите большой e1 событий в ведре А. Затем поместите следующее наибольшие e2 событие в ведре В. Поместить крупнейшее событие в ведре B, которое в большинстве e1-e2 минут длиной. Продолжайте добавлять в ковш B до тех пор, пока ваше ведро B не будет содержать не более A минут.

Затем повторите вышеизложенное (переход A для B).

Продолжайте повторять вышеуказанное, пока не завершите свои события.

Это будет работать только потому, что вы каждый ведро имеют одинаковую длину, 180 минут.

Фактически, поскольку у вас есть это правило 4-5 вечера, любые дополнительные события будут оставлены в конце. Они все пойдут в одном ведре, и это будет дневное ведро. Если по какой-то причине у вас есть событие, которое составляет> 180 минут, то это будет днем. Тогда, если вы поместите столько, сколько сможете утром (от самого большого до самого маленького), тогда остальное пойдет днем.