题目

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