最多可以参加的会议数目[贪心 + 优先队列]

前言

贪心是考察逻辑分析能力的好类型题目，犹如动态规划/单调栈/快慢双指针一样。贪心有一类题往往和优先队列挂钩，准确的说是和优先队列的优先挂钩。

一、最多可以参考的会议数目

二、贪心+优先队列

package everyday.medium;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

// 最多可以参加的会议数目。
public class MaxEvents {
    
    /* target:一共n个会议，每个会议都持续1天以上，我每天都能参加一个新会议，我最多能参加多少会议。 要能参加 最多 的会议，就必须在会议结束前 尽可能 的参加，就必须在每天选endDay 最小 的会议来开，不然错过了就可能后悔。 需要以每天为时间线，将当天开会日程的endDay加入优先队列，当天endDay小的开，开完踢出，在当天结束的会议踢出。 */

    public int maxEvents(int[][] events) {
    
        // 给开会按开始日期排个序，方便按顺序把第i天的endDay放入优先队列中，否则需要遍历数组，从O(1) -> O(N)。
        Arrays.sort(events, Comparator.comparingInt(o -> o[0]));
        PriorityQueue<Integer> minEndDay = new PriorityQueue<>();

        int curDay = 1;// 第一天
        int ans = 0;
        for (int i = 0; i < events.length || !minEndDay.isEmpty(); ) {
    
            // 把当天及当天前能开的，且没参加过的加入队列。
            while (i < events.length && curDay == events[i][0]) minEndDay.offer(events[i++][1]);
            // 取一个最小的
            if (!minEndDay.isEmpty()) {
    
                ans++;
                minEndDay.poll();
            }
            // 把当天结束的日程踢出队列。
            while (!minEndDay.isEmpty() && minEndDay.peek() == curDay) minEndDay.poll();
            // 开启下一天的会议选择。
            ++curDay;
        }
        // 每天选一个，有可能选到会议，有可能会议都还没开始，得到最后的开会次数。
        return ans;
    }
}

总结

1）贪心是考察逻辑分析能力的好题目，多练。
2）贪心很容易和优先队列的优先挂钩。

参考文献

[1] LeetCode 最多可以参加的会议数目