题解 | #主持人调度#

题目描述
有n个活动即将举办，每个活动都有活动的开始时间与活动的结束时间，第i个活动的开始时间是starti,第i个活动的结束时间是endi,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，活动主持人参与了第i个活动，那么该主持人在[starti,endi]这个时间段不能参与其他任何活动。求为了成功举办这n个活动，最少需要多少名主持人。

方法一：队列思想求解

求解思路
对于本题目关于主持人个数的求解，我们首先将start和end按时间的早晚进行排序。如果开始时间相同，则按结束时间进行排序。然后我们使用队列，如果当前开始时间大于等于之前某个活动的结束时间，说明可以让之前那个主持人继续主持当前的活动。否则，将当前活动的结束时间入队表示需要新增一个新的主持人。

图片说明

解题代码

class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
    {
        std::map<int, int> hycounter;
        for (auto &v : startEnd)
        {
            hycounter[v[0]]++; // v0的数目+1
            hycounter[v[1]]--; // v1的数目-1
        }
        int sum = 0; // 存储求和结果
        int hyres = 0; // 存储结果
        for (auto &v : hycounter)
        {
            sum += v.second;
            hyres = std::max(hyres, sum);
        }
        return hyres; // 返回结果
    }
};

复杂度分析
时间复杂度：使用快排函数的接口，因此其时间复杂度为 $O(NlogN)$
空间复杂度：使用队列queue，queue采用了堆结构，引入额外的内存地址空间，因此空间复杂度为 $O(K)$ ，其中K代表队列queue的大小。

方法二：贪心思想求解

求解思路
对于本题目，我们可以采用贪心的思想来进行求解。首先建立start数组和end数组用来记录时间。接着我们遍历start数组，判断当前开始时间是否大于等于最小的结束时间，如果是，则说明当前主持人可以搞定。如果否，则需要新增一个主持人，并将end数组下标后移。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        int[] hystart = new int[n]; // 初始化两个数组，分别记录开始时间和结束时间
        int[] hyend = new int[n];
        for(int i = 0;i<n;i++)
        {   //将活动的开始和结束时间赋值道start和end数组
            hystart[i] = startEnd[i][0];
            hyend[i] = startEnd[i][1];
        }
        //按从小到大的顺序对start和end数组排序
        Arrays.sort(hystart);
        Arrays.sort(hyend);
        int hyres = 0,index = 0;
        for(int i = 0;i<n;i++)
        {   //如果大于等于当前最小的结束时间，说明当前主持人可以搞定
            if(hystart[i] >= hyend[index])
            {
                index++;
            }
            //否则，需要新增主持人
            else
            {
                hyres++;
            }
        }
        return hyres; // 返回结果
    }
}

复杂度分析
时间复杂度：使用快排的接口，因此时间复杂度为 $O(NlogN)$
空间复杂度：引入start和end数组，因此空间复杂度为 $O(K)$ ，其中K代表start和end数组的大小。