Планирование событий Жадный

Question

Нам даны N диапазонов смещений дат, когда в организации присутствует N сотрудников. Что-то вроде
1-4 (т.е. сотрудник приедет на 1-й, 2-й, 3-й и 4-й день)
2-6
8-9
..
1-14
Мы должны организовать мероприятие с минимальным количеством дней, чтобы каждый сотрудник мог посетить мероприятие как минимум дважды. Пожалуйста, предложите алгоритм (возможно, жадный), чтобы сделать это.
PS: Событие - это однодневное мероприятие.

Answer 1

Если ваши данные невелики, вы можете просто перебрать их. Подберите все возможные комбинации за 2 дня. Попробуйте каждую комбинацию и посмотрите, сможет ли каждый присутствовать на обоих. Если нет, выберите все возможные комбинации за 3 дня, посмотрите, могут ли все присутствовать 2 из 3, и так далее. Это экспоненциально, но не может быть так плохо для ваших целей.

Жадный подход состоит в том, чтобы подсчитывать, сколько человек работает на работе каждый день, и выбирать день с максимальным количеством людей. Повторите, подсчитайте, сколько людей на работе каждый день , у которых еще нет двух запланированных событий, и выберите день с максимальным количеством людей. Конечно, не выбирайте один и тот же день дважды.

Answer 2

Я думаю, что это можно сделать с помощью следующего жадного подхода к событиям, отсортированным по дате окончания

Maintain a num count for all intervals. (Initialize all to 0)
If num = 0 place the two events on the last two days of this interval. 
If num = 1 place one event on the last day of this interval
If num = 2 already two events have been covered for this interval.

Размещение на событии в интервале может привести к увеличению числа num последующего события.