2020-02-16 16:24:19
问题描述：
问题求解：
看起来就像是sort + 贪心，但是具体如何做呢？
实际上本题是最大相容区间的变种题，在最大相容区间里，我们按照结束时间对interval进行排序，每次选择结束时间最早的进行安排。
这里其实也是一样，对每一天，我们在当天所有的events里挑选结束时间最早的进行安排即可。
如何维护当天所有的events呢？最常见的就是使用优先队列啦。
其实，就是扫描线算法。
public int maxEvents(int[][] events) {
int res = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((int[] o1, int[] o2) -> o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1]);
Arrays.sort(events, (int[] o1, int[] o2) -> o1[0] - o2[0]);
int idx = 0;
for (int day = 1; day <= 100000; day++) {
while (idx < events.length && events[idx][0] == day) {
pq.add(events[idx++]);
}
while (!pq.isEmpty() && pq.peek()[1] < day) pq.poll();
if (!pq.isEmpty()) {
pq.poll();
res += 1;
}
}
return res;
}
贪心-最大相容区间-Maximum Number of Events That Can Be Attended
原文：https://www.cnblogs.com/hyserendipity/p/12317308.html