Сложность: medium
Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi.
Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d.
Верните максимальное количество событий, которые вы можете посетить.
Пример:
Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4
👨💻 Алгоритм:
1⃣Сортировка событий по времени завершения:
Сначала отсортируйте массив событий по времени окончания каждого события в порядке возрастания. Это позволит сначала рассматривать события, которые заканчиваются раньше.
2⃣Использование множества для отслеживания посещенных дней:
Создайте множество для хранения дней, в которые уже были посещены события. Это позволит легко проверять, был ли день уже использован для посещения другого события.
3⃣Посещение событий в доступные дни:
Пройдитесь по отсортированному массиву событий. Для каждого события проверьте каждый день от начала события до его окончания и найдите первый доступный день, который еще не был использован. Если такой день найден, добавьте его в множество и увеличьте счетчик посещенных событий.
😎 Решение:
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
events.sort(key=lambda x: x[1])
visited_days = set()
count = 0
for start, end in events:
for day in range(start, end + 1):
if day not in visited_days:
visited_days.add(day)
count += 1
break
return count
Ставь 👍 и забирай 📚 Базу знаний