贪心之主持人调度

package com.zhang.reflection.面试.算法模版.贪心算法;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，
 * 第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
 *
 * 一位活动主持人在同一时间只能参与一个活动。
 * 并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，
 * 那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
 * 2,[[1,2],[2,3]]
 * 1
 * 只需要一个主持人就能成功举办这两个活动
 */
public class 主持人调度 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        //方法一：缺点，对数组排序时，由于整形长度限制，如果两个数相减时（x[1]-y[1]），可能会出现溢出，导致排序错误
        //方法二：为了解决方法一中出现的溢出问题，对整形扩张为长整型，然后重新编写Comparator接口中的Compare方法。
        //转换长整型
        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();//返回优先队列的大小即为最小的主持人数量
    }
}