题目
给你一个数组 events
,其中 events[i] = [startDay, endDay]
,表示会议 i
开始于 startDay
,结束于 endDay
。
你可以在满足 startDay <= d <= endDay
中的任意一天 d
参加会议 i
。注意,一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目。
思路
根据开始时间将 events 数组排序,然后选择在范围内的结束时间最早的会议。
代码
public int maxEvents(int[][] events) { //首先排序:开始时间小的在前。这样是方便我们顺序遍历,把开始时间一样的都放进堆 Arrays.sort(events, (o1, o2) -> o1[0] - o2[0]); //小顶堆 PriorityQueue<Integer> pq = new PriorityQueue<>(); //结果、开始时间、events下标、有多少组数据 int res = 0, last = 1, i = 0, n = events.length; while (i < n || !pq.isEmpty()) { //将start相同的会议都放进堆里 while (i < n && events[i][0] == last) { pq.offer(events[i++][1]); } //pop掉当前天数之前的 while (!pq.isEmpty() && pq.peek() < last) { pq.poll(); } //顶上的就是俺们要参加的 if (!pq.isEmpty()) { pq.poll(); res++; } last++; } return res; }