题解 | #主持人调度#

主持人调度

1、题意重述

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

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

换句话说，就是求最少的主持人数，使得活动能够正常进行。(ps：同一时间，主持人只能参加一个活动)

2、思路整理

使用贪心的思想：

Step1：建立两个数组start和end分别记录活动的开始和结束时间。

Step2：对Start和end进行排序。

Step3：遍历Start数组，用贪心思想，下一场活动的开始时间晚于本场活动的结束时间，就不换主持人，否则，添加一个主持人。最后返回结果。

3、代码实现

import java.util.*;

public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        //初始化两个数组
        int[] start=new int[n];
        int[] end=new int[n];
        for(int i=0;i<n;i++){
            start[i]=startEnd[i][0];
            end[i]=startEnd[i][1];
        }
        //排序
        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;//返回结果
    }
}

4、复杂度分析

时间复杂度：使用快排，因此时间复杂度为$O(NlogN)O(NlogN)$。

空间复杂度：使用了start和end数组，因此空间复杂度为$O(N)O(N)$，其中N为数组的大小。