Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i -й матч начинается в момент времени l i и заканчивается в момент времени r i . Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени r i , то она может после него посмотреть любой матч j , который начинается не раньше момента времени r i , то есть l j ≥ r i (Василиса может моментально переключить каналы в момент окон

Для решения этой задачи можно использовать жадный алгоритм.

Шаги решения:

1. Создаем список матчей, где каждый матч представлен кортежем из начального и конечного времени.

2. Сортируем список матчей по конечному времени в порядке возрастания.

3. Создаем пустой список результатов, в который будем добавлять матчи.

4. Итерируемся по отсортированному списку матчей.

5. Проверяем, если список результатов пуст или конец последнего матча в списке результатов меньше начала текущего матча, то добавляем текущий матч в список результатов.

6. Иначе, если начало текущего матча больше или равно концу последнего матча в списке результатов, то заменяем последний матч в списке результатов на текущий матч.

7. По окончанию итерации по всем матчам, в списке результатов будут находиться матчи, которые можно посмотреть последовательно с максимальным количеством.

8. Выводим список результатов.

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

Сложность алгоритма: O(n*log(n)), где n – количество матчей.