Java | LeetCode
Задача: 1353. Maximum Number of Events That Can Be Attended
Сложность: 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⃣Посещение событий в доступные дни:
Пройдитесь по отсортированному массиву событий. Для каждого события проверьте каждый день от начала события до его окончания и найдите первый доступный день, который еще не был использован. Если такой день найден, добавьте его в множество и увеличьте счетчик посещенных событий.
😎 Решение:
import java.util.*;
public class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, Comparator.comparingInt(e -> e[1]));
Set<Integer> visitedDays = new HashSet<>();
int count = 0;
for (int[] event : events) {
for (int day = event[0]; day <= event[1]; day++) {
if (!visitedDays.contains(day)) {
visitedDays.add(day);
count++;
break;
}
}
}
return count;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 367 ·