讨论/题目交流/🏆 第 176 场力扣周赛/
🏆 第 176 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 统计有序矩阵中的负数
5 分 - 最后 K 个数的乘积
5 分 - 最多可以参加的会议数目
6 分 - 多次求和构造目标数组

展开讨论

第三题解法分享(贪心+优先队列)

5342. 最多可以参加的会议数目

这道题本来以为简单的贪心可以做,尝试了几次,发现总是不能处理某些情况的输入。最后发现还是得用优先队列结合贪心法来做。

优先队列的做法是模拟一个人的日程:第一天的时候,查看所有已经开始、还未参加的会议,找出其中将会最早结束的会议。注意一天只能参加一个会议。每一天都这样决策的话,最后就可以参加最多数量的会议。

那么,我们的优先队列中存储所有到当前日期为止的所有已经开始、还未参加的会议。当新的一天到来时,队列中加入新开始的会议;而这一天参加了某个会议,就将会议从队列中删除。

根据以上的分析,优先队列的排序条件是:按照会议的结束时间排序。而会议进入队列的顺序是按照会议的开始时间,所以在一开始需要对会议数组做一个排序。

代码如下:

public int maxEvents(int[][] events) {
    // 会议按照开始时间排序
    Arrays.sort(events, (e1, e2) -> Integer.compare(e1[0], e2[0]));

    // 优先队列按照结束时间排序
    PriorityQueue<int[]> pq = new PriorityQueue<>((e1, e2) -> Integer.compare(e1[1], e2[1]));

    int N = events.length;
    int i = 0;
    int d = 1;
    int count = 0;
    while (i < N || !pq.isEmpty()) {
        // 模拟第 d 天的决策
        // 将已经开始的会议加入队列
        while (i < N && events[i][0] <= d) {
            pq.add(events[i]);
            i++;
        }

        // 找出一个可以参加的最早结束的会议
        while (!pq.isEmpty()) {
            int[] e = pq.poll();
            if (e[1] >= d) {
                count++;
                break;
            }
        }
        d++;
    }

    return count;
}
4
展开全部 24 讨论