BM96　主持人调度（二）¶

中等通过率 23.87%python3核心代码模式样例通过牛客 AC贪心

讲解章节：贪心

一句话

开始时间与结束时间各自排序后双指针，数「没人可复用」的次数。

解题思路¶

这题考什么¶

先做一次模型归约：最少主持人数 = 同一时刻最多有几个活动在同时进行，也就是区间的最大重叠层数。某一瞬间有 k 个活动重叠就非得 k 个人；反过来只要任何时刻重叠都不超过 k，贪心地「谁先空出来谁接下一场」就一定能用 k 个人排完。见贪心。

做法一（本文实现，双指针）：把所有开始时间排成数组 starts、所有结束时间排成数组 ends——打散原本的配对关系是允许的，因为归约之后只关心「到某个时刻为止开了几场、散了几场」这个计数，与谁配谁无关。然后按开始时间顺序逐个安排活动，用 j 指向「最早的那个还没被认领的散场时间」：

for i in range(n):
    starts[i] >= ends[j]:  已经有主持人在此之前（或恰好此刻）空出来 -> 复用，j += 1
    否则:                  谁都没空 -> 再请一位，res += 1

比较用 >= 而非 >：前一个活动结束的那一瞬间下一个可以立刻开始（样例 1 的 [1,2] 与 [2,3] 只要 1 人）。题面把占用写成开区间 (start, end)，端点不算冲突。

循环里 j 只在 i 前进时才可能加一，所以恒有 j <= i < n，读 ends[j] 不会越界；最终 res = n - j，正好是「被迫新增主持人」的次数，也就是最大重叠层数。

做法二（最小堆）：按开始时间排序，堆里存「占用中的活动的结束时间」。每来一个活动，若堆顶结束时间 <= 它的开始时间，说明那位主持人已经空出来了，弹出复用；然后把自己的结束时间压进去。堆的大小峰值就是答案。两种写法都是 O(n log n)，双指针常数更小、代码更短。

手推 [[1,3],[2,4]]：starts = [1,2]，ends = [3,4]

i=0  1 >= 3? 否 -> 新请一位  res=1
i=1  2 >= 3? 否 -> 新请一位  res=2   -> 答案 2

数据规模与复杂度¶

n <= 1e5，时间戳满足 start_i <= end_i 且都在 int 范围内（题面给到 -2^32 一侧），时限「其他语言 4 秒」，题面要求时间 O(n log n)、空间 O(n)。本解两次排序是瓶颈，扫描只有 O(n)，空间 O(n) 存两份时间戳。朴素的「对每个活动去数有多少个区间与它相交」是 O(n^2) = 1e10，不可行。

坑在哪¶

start == end 的零长活动是合法输入（题面只保证 start_i <= end_i）。全是这种活动时，每一轮 starts[i] >= ends[j] 都成立，res 会一路停在 0，而题面要求 n >= 1 时至少有一位主持人，所以末尾要用 max(res, 1) 兜底。反过来说，只要输入里没有零长活动，starts[0] < ends[0] 必然成立， res 至少是 1，这层兜底不会改变正常数据的答案。
换成朴素的「开场记 +1、散场记 -1，排序后扫事件」写法要格外小心同刻事件的处理次序：零长活动的散场事件若排在自己的开场事件之前，在场计数会先掉到 -1 再回到 0，峰值随之算少，用计数当下标去写数组的变体还会直接越界。本文这种「两列时间戳各自排序」的写法不受事件次序影响。
打散配对之后仍然正确，靠的是第一段那个归约。若题目改成要输出「谁主持哪几场」，配对关系就不能丢，得换成最小堆的写法。
j 不需要额外的越界判断，但那是因为 j <= i 这条循环不变量成立。把 j += 1 挪出 if 分支（每轮无条件推进）就会读到 ends[n]，直接 IndexError。
参数 n 与 len(startEnd) 一致，循环按 n 走；n <= 0 或空数组先短路返回 0，否则 ends[0] 会在空列表上越界。

参考实现¶

solutions/nowcoder/BM96/sol.py
from typing import List, Optional


class Solution:
    def minmumNumberOfHost(self, n: int, startEnd: List[List[int]]) -> int:
        # 空输入先挡住，否则下面读 ends[0] 会越界
        if n <= 0 or not startEnd:
            return 0
        # 两列时间戳各自排序，故意打散配对关系：归约之后只关心开场与散场的计数，
        # 与谁配谁无关。这也让结果不受同一时刻事件先后次序的影响
        starts = sorted(x[0] for x in startEnd)
        ends = sorted(x[1] for x in startEnd)
        res = 0
        j = 0                            # 最早那个还没被认领的散场时间；恒有 j <= i
        # 按开场时间顺序逐个安排，每一步只问「有没有人已经腾出手」
        for i in range(n):
            # 用 >= 而非 >：上一场结束的那一瞬间下一场可以立刻开始，端点不算冲突
            if starts[i] >= ends[j]:
                j += 1                   # 复用这位主持人，人数不增；j 只在这里推进，故不会越界
            else:
                res += 1                 # 谁都没空，只能再请一位
        # n >= 1 时至少要一位主持人。全是 start == end 的零长活动会让 res 停在 0，
        # 这一层兜底专治那种退化输入，对正常数据不起作用
        return max(res, 1)

BM96 主持人调度（二）¶