LEETCODE 1353. Maximum Number of Events That Can Be Attended 解题思路分析

题目大意:

最多可以参加的会议数目

给你一个数组 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

示例 3:

输入:events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
输出:4

示例 4:

输入:events = [[1,100000]]
输出:1

示例 5:

输入:events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
输出:7

提示:

  • 1 <= events.length <= 10^5
  • events[i].length == 2
  • 1 <= events[i][0] <= events[i][1] <= 10^5

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1353

解题思路分析:

我们先理清题目给出的条件:

  1. 每天最多只能参加一个会议
  2. 每个会议不需要全程出席,参加一天即可
  3. 求最多可以参加多少会议

对于任意一天,我们能参加的会议必须是当前正在进行的会议,尚未开始或者已经结束的会议是无法参加的。另外,如果一天中有多个会议在同时召开,我们应该优先选择结束时间最早的会议去参加,相对较晚结束的会议我们之后仍有时间去出席。

解题时,我们按照天数来做循环,首先将当天开始的会议都加载到一个PriorityQueue中,Queue中的元素排列按照会议结束时间升序排序。然后我们将所有已经结束的会议从Queue中删除,保证Queue中都是当天正在召开的会议。这时如果Queue中元素个数大于0(存在当天正在召开的会议),那么从Queue中取出一个结束时间最早的会议去参加,此时参加会议数加一。之后循环至下一天重复上述操作即可。

实现代码:

public int maxEvents(int[][] events) {
    // 将所有会议按照开始时间升序排序
    Arrays.sort(events,(a,b)->a[0]-b[0]);
    // 使用Queue来保存当前正在召开的会议的结束时间,按照升序排序
    PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->a-b);
    // 返回结果
    int res=0;
    // 当前遍历到的会议下标
    int index=0;
    // 循环每一天
    for(int day=1;day<=100000;day++){
        // 如果已遍历完所有会议,并且Queue中元素个数为0,退出
        if(index>=events.length&&q.size()==0) break;
        // 取出当天开始的会议加入到Queue中
        for(;index<events.length;index++){
            int[] e = events[index];
            if(e[0]<=day) q.offer(e[1]);
            else break;
        }
        // 从Queue中删除已经结束的会议
        while(q.size()>0 && q.peek()<day){
            q.poll();
        }
        // 如果Queue不为空
        if(q.size()>0){
            // 从Queue中取出一个最早结束的会议
            q.poll();
            // 会议参加数加一
            res++;
        }
    }
    return res;
}

本题解法执行时间为40ms。

Runtime: 40 ms, faster than 94.32% of Java online submissions for Maximum Number of Events That Can Be Attended.

Memory Usage: 70.6 MB, less than 100.00% of Java online submissions for Maximum Number of Events That Can Be Attended.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1353-maximum-number-of-events-that-can-be-attended-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。