最多可以参加的会议数目
难度:
标签:
题目描述
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目。
示例 1：
输入：events = [[1,2],[2,3],[3,4]] 输出：3 解释：你可以参加所有的三个会议。 安排会议的一种方案如上图。 第 1 天参加第一个会议。 第 2 天参加第二个会议。 第 3 天参加第三个会议。
示例 2：
输入：events= [[1,2],[2,3],[3,4],[1,2]] 输出：4
提示：
1 <= events.length <= 105events[i].length == 21 <= startDayi <= endDayi <= 105
代码结果
运行时间: 164 ms, 内存: 49.3 MB
/* 思路：
1. 按照会议的结束日期对events进行排序。
2. 使用一个Set记录已经参加会议的日期。
3. 依次遍历每个会议，选择可以参加的最早的日期。 */
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
public class MaxEventsStream {
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> a[1] - b[1]);
Set<Integer> attended = new HashSet<>();
return Arrays.stream(events)
.flatMapToInt(event -> IntStream.rangeClosed(event[0], event[1]))
.filter(day -> attended.add(day))
.limit(events.length)
.toArray()
.length;
}
}解释
方法:
此题解采用贪心算法和优先队列（最小堆）来解决问题。首先，将会议按照开始时间进行排序。使用一个优先队列来存储当前可以参加的会议的结束时间。对于每一天，从优先队列中选择结束时间最早的会议参加。这样做可以最大限度地留下空间为后续的会议。如果当前最早结束的会议已经不能参加（即结束时间小于当前日期），则将其从队列中移除。重复此过程，直到所有会议都被处理或参加。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
代码中对于当前日期`today`的更新逻辑为何设置成`today = max(today, events[i][0])`？这样做有什么具体的作用？
▷