题解 | 主持人调度（二）

1、解题思路

这是一个典型的区间调度问题，可以通过贪心算法来解决。具体步骤如下：

1. 排序活动：首先将所有的活动按照结束时间进行排序。如果结束时间相同，可以按开始时间排序。
2. 贪心选择 ：使用一个优先队列（最小堆）来记录当前正在进行活动的结束时间。 遍历排序后的活动，对于每个活动，检查堆顶的结束时间是否小于等于当前活动的开始时间。如果是，则可以将该主持人用于当前活动，更新堆顶的结束时间。如果不是，则需要新增一个主持人，将当前活动的结束时间加入堆中。
3. 结果：最终堆的大小即为所需主持人的最小数量。

这种方法确保我们尽可能多地复用主持人，从而最小化主持人的总数。

2、代码实现

C++

#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        // write code here
        if (startEnd.empty()) {
            return 0;
        }

        // 按照开始时间排序
        sort(startEnd.begin(), startEnd.end(), [](const vector<int>& a,
        const vector<int>& b) {
            return a[0] < b[0];
        });

        // 最小堆, 存储结束时间
        priority_queue<int, vector<int>, greater<int>> minHeap;
        minHeap.push(startEnd[0][1]);

        for (int i = 1; i < startEnd.size(); ++i) {
            // 如果当前活动的开始时间大于等于堆顶的结束时间, 可以复用主持人
            if (startEnd[i][0] >= minHeap.top()) {
                minHeap.pop();
            }
            minHeap.push(startEnd[i][1]);
        }

        return minHeap.size();
    }
};

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算成功举办活动需要多少名主持人
# @param n int整型 有n个活动
# @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
# @return int整型
#
import heapq

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        if not startEnd:
            return 0
        
        # 按照开始时间排序
        startEnd.sort(key=lambda x: x[0])
        
        # 最小堆，存储结束时间
        min_heap = []
        heapq.heappush(min_heap, startEnd[0][1])
        
        for i in range(1, len(startEnd)):
            # 如果当前活动的开始时间大于等于堆顶的结束时间，可以复用主持人
            if startEnd[i][0] >= min_heap[0]:
                heapq.heappop(min_heap)
            heapq.heappush(min_heap, startEnd[i][1])
        
        return len(min_heap)

3、复杂度分析

1. 排序活动：按照开始时间排序，以便后续贪心选择。
2. 最小堆：用于动态维护当前正在进行活动的结束时间，确保可以及时复用主持人。
3. 贪心选择：每次尽可能复用最早结束的主持人，从而减少新增主持人的数量。
4. 时间复杂度：排序O(n log n)，堆操作O(n log n)，总时间复杂度O(n log n)。
5. 空间复杂度：堆的大小最多为n，O(n)。