[NC]147. 主持人调度

🚩传送门：牛客题目

题目

有个活动即将举办，每个活动都有开始时间与活动的结束时间，第 个活动的开始时间是 ,第个活动的结束时间是 ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第个活动，那么该主持人在 ( ) 这个时间段不能参与其他任何活动。求为了成功举办这个活动，最少需要多少名主持人。

数据范围: ，
复杂度要求：时间复杂度 ，空间复杂度

示例1

输入：2,[[1,3],[2,4]] 返回值：2

解题思路：贪心

首先，要对活动进行排序：

• 开始时间相等的，结束时间从小到大
• 开始时间不相等的，开始时间从小到大

  int[][] startEnd = new int[][]{{1,2},{2,5},{2,3}};
  Arrays.sort(startEnd,new Comparator<int[]>(){
   public int compare(int[] arr1,int[] arr2){
       if(arr1[0] == arr2[0]){
           return arr1[1] - arr2[1];
       }
       return arr1[0] - arr2[0];
   }
  });

  int[][] startEnd = new int[][]{{1,2},{2,5},{2,3}};
  Arrays.sort(startEnd,(o1,o2)->{
   return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
  });

  但是这个会有问题，对于负数，**整数-负数**得到1，导致也会交换，负数被扔到了后面
  
  因此先判断正负再排序

  Arrays.sort(startEnd,(o1,o2)->{
   if(o1[0] > 0 && o2[0] < 0) return 1;
   if(o1[0] < 0 && o2[0] > 0) return -1;
   return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
  });

  
  得到了有序活动时间后，我们可以使用线程池的思想，每遇到一场活动，我们就跟分配内存一样，去主持人池子里查找一下，有没有空闲的主持人将他分配给这个活动，当所有主持人都有活动的时候，在重新开辟一个新的主持人出来主持新的活动 。

复杂度分析

时间复杂度：，其中 是主持人个数， 是活动场数。

空间复杂度：，其 是活动场数。

我的代码

public class Solution {
    public boolean checkPerSon(int[]ans,int startTime,int endTime){
        // 主持人线程池
        for(int i=1;i<=ans[0];i++){
            // 当前是否有主持人空闲
            if(ans[i]<=startTime){
                ans[i]=endTime;
                return true;
            }
        }
        ans[0]++;             // 新增一个主持人
        ans[ans[0]]=endTime; // 记录新增主持人的结束时间
        return false;
    }
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        if(startEnd==null) return 0;
        if(startEnd.length==1) return 1;
        Arrays.sort(startEnd,(o1,o2)->{
           if(o1[0] > 0 && o2[0] < 0) return 1;
           if(o1[0] < 0 && o2[0] > 0) return -1;
           return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
        });
        // 主持人池子
        int[] ans=new int[startEnd.length+1];
        ans[0]=1;               // 0 位标志位,存储主持人个数
        ans[1]=startEnd[0][1]; // 记录第一场结束时间
        // 遍历所有的活动
        for(int i=1;i<startEnd.length;i++){
            // 调用checkPerSon检查分配空余主持人
            checkPerSon(ans,startEnd[i][0],startEnd[i][1]);    
        }
        return ans[0];
    }
}

这个复杂度显然是不满足时间复杂度 ，空间复杂度

因此我们可以利用优先队列（堆）来进行优化，每次自动吐出一个结束时间最早的主持人出来，让他主持新的活动，每次调整一个新的主持人时间复杂度是，一共吐出 个活动主持人，因此总的时间复杂度是。

🚩我的代码 [ 优先队列 ]

public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here
        if(startEnd==null) return 0;
        if(startEnd.length==1) return 1;
        Arrays.sort(startEnd,(o1,o2)->{
           if(o1[0] > 0 && o2[0] < 0) return 1;
           if(o1[0] < 0 && o2[0] > 0) return -1;
           return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
        });
        PriorityQueue<Integer> pQueue =new PriorityQueue<>();
        pQueue.add(Integer.MIN_VALUE);
        for(int i=0;i<startEnd.length;i++){
            if(pQueue.peek()<=startEnd[i][0]){    // 有空闲的主持人
                pQueue.poll();    // 将该主持人出队,出去更换新的活动信息
            }
             pQueue.offer(startEnd[i][1]);    // 插入新的活动信息的主持人
        }
        return pQueue.size();
    }
}