题解 | 主持人调度（二）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        Arrays.sort(startEnd, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] > o2[0]) {
                    return 1;
                } else if (o1[0] == o2[0]) {
                    if (o1[1] > o2[1]) {
                        return 1;
                    } else {
                        return -1;
                    }
                } else {
                    return -1;
                }
            }
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int[] ints = startEnd[i];
            if (pq.isEmpty()) {
                pq.add(ints[1]);
            } else {
                Integer peek = pq.peek();
                //如果开始时间小于结束时间
                if (ints[0] < peek) {
                    pq.add(ints[1]);
                } else {
                    pq.poll();
                    pq.add(ints[1]);
                }
            }
        }
        return pq.size();
    }
}

第一步根据开始时间(第一优先级)和结束时间(第二优先级，开始时间相同的结束时间早的排前面)排序。

这里采用小顶堆(最小的会出现在最上面)来做。

以{{1，2}，{2，3}}为例

先把第一个的结束时间放入堆里，此时堆顶是2.

此时遇到了第二个数据{2，3}.

堆顶是2，结束时间也是2，所以还可以用这个主持人

把这个堆顶元素弹出，修改成结束时间后加入回去，此时堆顶元素变成3.

遍历结束，此时堆里只有一个元素，返回1.

再以{{1，3}，{2，4}}为例

第一次把3压入。

遇到了第二{2，4}的时候，堆顶的元素是3

2<3，所以活动还没有结束，需要新开一个，把结束时间4压入。

此时堆里有2个元素了，返回2

如果此时再来一个{3，5}.

此时堆顶元素是3，

3=3，所以，不需要新开一个，直接把3弹出，把结束时间5压入。

此时堆里还是2个值。