05 August 2008
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
请返回你可以参加的 最大 会议数目。
贪心 + 最小堆(优先队列）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int maxEvents(int[][] events) {
// 将会议按开始时间排序
Arrays.sort(events, Comparator.comparingInt(a -> a[0]));
// 小顶堆，存放会议结束时间
PriorityQueue<Integer> queue = new PriorityQueue<>();
int result = 0;
int start = events[0][0]; // 会议开始时间
int index = 0; // 会议下标
// 还有会议没开始 或者 还有会议没结束
while (index < events.length || !queue.isEmpty()) {
// 把开始时间相同的，放入堆中，比较结束时间
while (index < events.length && events[index][0] == start) {
queue.offer(events[index][1]);
index++;
}
// 把开始时间之前已经结束掉的，删掉
while (!queue.isEmpty() && queue.peek() < start) {
queue.poll();
}
// 如果栈不空，还有会议没结束，那么栈顶，就是结束时间最早的会议，参加他
if (!queue.isEmpty()) {
queue.poll();
result++;
}
// 开始时间往后排一天
start++;
}
return result;
}
}