题解 | #主持人调度#

题意整理

• 有n个活动即将举办，每个活动都有一个开始时间和结束时间。
• 现在派若干个主持人来主持活动，要求每一个主持人主持的活动中，各个活动的时间段（开始时间到结束时间）不重叠。

方法一（优先队列）

1.解题思路

• 首先对startEnd按开始时间从小到大排序，如果开始时间相同，则按结束时间排序。
• 然后初始化一个优先队列。
• 如果当前开始时间大于等于之前某个活动的结束时间，说明可以让之前那个主持人继续主持当前的活动；否则，将当前活动的结束时间入队，表示需要新派一个主持人。

动图展示：

2.代码实现

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,(o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);

        //初始化优先队列
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int[] activity:startEnd){
            //如果当前开始时间大于等于之前某个活动的结束时间，说明可以让之前那个主持人继续主持当前的活动
            if(!queue.isEmpty()&&queue.peek()<=activity[0]){
                queue.poll();
            }
            //如果不满足，需要新派一个主持人
            queue.offer(activity[1]);
        }

        return queue.size();

    }
}

3.复杂度分析

• 时间复杂度：首先sort()接口的时间复杂度是 ，而优先队列queue是一个小顶堆，插入与移除的时间复杂度都是，总共需要操作n次，所以时间复杂度为。
• 空间复杂度：最坏情况下，需要额外大小为n的堆存储结束时间，所以空间复杂度为。

方法二（排序+贪心）

1.解题思路

• 首先建立两个数组分别存储开始时间（记为start）和结束时间（记为end）。
• 然后分别对start和end数组进行排序。
• 接着遍历start数组，判断当前开始时间是否大于等于最小的结束时间，如果是，则说明当前主持人就可以搞定（对应当前最小的结束时间的那个活动）；如果否，则需要新增一个主持人，并将end数组下标后移（表示对应的活动已经有人主持）。

2.代码实现

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) {
        //初始化两个数组，分别记录开始时间和结束时间
        int[] start=new int[n];
        int[] end=new int[n];

        //将活动的开始和结束时间赋值道start和end数组
        for(int i=0;i<n;i++){
            start[i]=startEnd[i][0];
            end[i]=startEnd[i][1];
        }

        //按从小到大的顺序对start和end数组排序
        Arrays.sort(start);
        Arrays.sort(end);

        int res=0,index=0;
        for(int i=0;i<n;i++){
            //如果大于等于当前最小的结束时间，说明当前主持人可以搞定
            if(start[i]>=end[index]){
                index++;
            }
            //否则，需要新增主持人
            else{
                res++;
            }
        }

        return res;

    }
}

3.复杂度分析

• 时间复杂度：需要进行排序，排序接口的时间复杂度是，所以时间复杂度为。
• 空间复杂度：需要额外大小为n的start和end数组，所以空间复杂度为。