题解 | #主持人调度#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    @SuppressWarnings("unchecked")
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        //方法一：缺点，对数组排序时，由于整形长度限制，如果两个数相减时（x[1]-y[1]），可能会出现溢出，导致排序错误
        //方法二：为了解决方法一中出现的溢出问题，对整形扩张为长整型，然后重新编写Comparator接口中的Compare方法。
//         Arrays.sort(startEnd,(x,y)->{
//             return x[0] == y[0]?x[1]-y[1]:x[0]-y[0];//升序排列
//         });
        
//         PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//         priorityQueue.offer(startEnd[0][1]);
//         for(int i=1;i<n;i++){
//             if(startEnd[i][0] >= (int)priorityQueue.peek()){
//                 priorityQueue.poll();
//             }
//             priorityQueue.offer(startEnd[i][1]);
//         }
        //转换长整型
        long[][] c = new long[n][2];
        for(int i=0;i<n;i++){
            for(int j=0;j<2;j++){
                c[i][j] = startEnd[i][j];
            }
        }
        //排序
        Arrays.sort(c,(x,y)->{//重新编写Comparator接口中的Compare方法
            if(x[0]==y[0]){//先比较活动的开始时间，如果活动的开始时间相等，再比较活动的结束时间
                return x[1]<y[1]?-1:(x[1]==y[1]?0:1);//升序
            }else{
                return x[0]<y[0]?-1:(x[0]==y[0]?0:1);//升序
            }
        });
        
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();//创建一个优先队列
        priorityQueue.offer(c[0][1]);//压入第一个活动的结束时间
        for(int i=1;i<n;i++){//从第一个往后遍历
            //如果后面的活动的开始时间比前面的活动的结束时间后，则表示可以由同一个主持人主持
            if(c[i][0] >= priorityQueue.peek()){
                priorityQueue.poll();//弹出当前活动的结束时间
            }
            priorityQueue.offer(c[i][1]);//压入当前活动的后一个活动的结束时间
        }
        
        return priorityQueue.size();//返回优先队列的大小即为最小的主持人数量
    }
}