Максимум непересекающихся встреч: по какому полю сортировать
Есть список встреч с временем начала и конца. Нужно выбрать максимальное количество встреч, которые не пересекаются между собой. Какая жадная стратегия даёт гарантированно оптимальный ответ?
- Сортировать по времени начала и брать каждую встречу, которая не конфликтует с уже выбранными
- Сортировать по длительности и брать сначала самые короткие: они занимают меньше места в календаре
- Сортировать по времени окончания и брать встречу, если её начало не раньше конца последней взятой
- Жадность здесь неприменима: нужна динамика по интервалам с поиском последней совместимой встречи