牛客题解-在线编程-面试笔刷：BM96 主持人调度（二）Python解法 ...

形貌：
有                                   n                              n                  n个活动即将举办，每个活动都有开始时间与活动的结束时间，第                                   i                              i                  i个活动的开始时间是                                   s                         t                         a                         r                                   t                            i                                       start_i                  starti​，第                                   i                              i                  i个活动的结束时间是                                   e                         n                                   d                            i                                       end_i                  endi​，举办某个活动就必要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人必要全程参与活动，换句话说，一个主持人参与了第                                   i                              i                  i个活动，那么该主持人在                                   (                         s                         t                         a                         r                                   t                            i                                  ,                         e                         n                                   d                            i                                  )                              (start_i,end_i)                  (starti​,endi​)这个时间段不能参与其他任何活动。求为了成功举办这                                   n                              n                  n个活动，最少必要多少名主持人。
数据范围：                                   1                         ≤                         n                         ≤                         1                                   0                            5                                       1 \leq n \leq 10^5                  1≤n≤105，                                   −                                   2                            32                                  ≤                         s                         t                         a                         r                                   t                            i                                  ≤                         e                         n                                   d                            i                                  ≤                                   2                            31                                  −                         1                              -2^{32} \leq start_i \leq end_i \leq 2^{31} - 1                  −232≤starti​≤endi​≤231−1
复杂度要求：时间复杂度                                   O                         (                         n                         log                         ⁡                         n                         )                              O(n \log n)                  O(nlogn)，空间复杂度                                   O                         (                         n                         )                              O(n)                  O(n)
示例1
输入：                                   2                         ,                         [                         [                         1                         ,                         2                         ]                         ,                         [                         2                         ,                         3                         ]                         ]                              2, [[1,2],[2,3]]                  2,[[1,2],[2,3]]
返回值：                                   1                              1                  1
说明：只必要一个主持人就能成功举办这两个活动
示例2
输入：                                   2                         ,                         [                         [                         1                         ,                         3                         ]                         ,                         [                         2                         ,                         4                         ]                         ]                              2, [[1,3],[2,4]]                  2,[[1,3],[2,4]]
返回值：                                   2                              2                  2
说明：必要两个主持人才气成功举办这两个活动
备注：
                                    1                         ≤                         n                         ≤                         1                                   0                            5                                       1 \leq n \leq 10^5                  1≤n≤105
                                    s                         t                         a                         r                                   t                            i                                  ,                         e                         n                                   d                            i                                       start_i,end_i                  starti​,endi​在                                   i                         n                         t                              int                  int范围内
题解

为了实现找到成功举办这 n 个活动所需的最少主持人数量的功能，并且满足时间复杂度                                    O                         (                         n                         log                         ⁡                         n                         )                              O(n \log n)                  O(nlogn) 和空间复杂度                                    O                         (                         n                         )                              O(n)                  O(n) 的要求，我们可以采用以下思路：
思路

• 分离开始时间和结束时间：将全部活动的开始时间和结束时间分别存储在两个数组中，并对这两个数组进行排序。
  
• 双指针遍历：利用两个指针分别遍历开始时间数组和结束时间数组，通过比力当前开始时间和结束时间来判定是否必要新增主持人。
  
• 动态调整主持人数量：当开始时间早于结束时间时，必要新增一个主持人；当开始时间晚于或等于结束时间时，说明有一个主持人可以被开释，不必要新增主持人。
  

代码实现

1. from typing import List
3. class Solution:
4.     def minmumNumberOfHost(self, n: int, startEnd: List[List[int]]) -> int:
5.         # 分离开始时间和结束时间
6.         start_times = sorted([start for start, _ in startEnd])
7.         end_times = sorted([end for _, end in startEnd])
8.         
9.         # 初始化指针和主持人数量
10.         start_ptr = 0
11.         end_ptr = 0
12.         max_hosts = 0
13.         current_hosts = 0
14.         
15.         # 双指针遍历
16.         while start_ptr < n:
17.             if start_times[start_ptr] < end_times[end_ptr]:
18.                 # 如果开始时间早于结束时间，需要新增一个主持人
19.                 current_hosts += 1
20.                 start_ptr += 1
21.             else:
22.                 # 如果开始时间晚于或等于结束时间，有一个主持人可以被释放
23.                 current_hosts -= 1
24.                 end_ptr += 1
25.             
26.             # 更新最大主持人数量
27.             max_hosts = max(max_hosts, current_hosts)
28.         
29.         return max_hosts

复制代码

为什么不必要确保开始时间和结束时间一一对应？

在代码中，分离开始时间和结束时间后分别进行排序，固然排序后开始时间数组和结束时间数组里元素的顺序被打乱，但我们并不必要确保开始时间和结束时间一一对应，下面具体解释缘故原由：
原数据结构与排序目的

最初的输入数据 startEnd 是一个二维列表，其中每个子列表 [start, end] 代表一个活动的开始时间和结束时间，它们是一一对应的。然而，在解决这个最少主持人数量的问题时，我们并不关心具体哪个开始时间对应哪个结束时间，只关注全部活动的开始和结束时间的整体时间线分布。
将开始时间和结束时间分别提取出来并排序，目的是为了构建两个有序的时间序列，一个代表全部活动开始的时间点，另一个代表全部活动结束的时间点。通过这两个有序序列，我们可以模拟活动在时间轴上的进行过程，进而计算出所需主持人的最少数量。
双指针遍历的逻辑

排序完成后，利用双指针 start_ptr 和 end_ptr 分别遍历开始时间数组 start_times 和结束时间数组 end_times，具体逻辑如下：

• 当 start_times[start_ptr] < end_times[end_ptr] 时，意味着在当前时间点有一个新的活动开始了，而之前的某个活动还未结束，此时没有空闲的主持人，必要新增一个主持人。然后将 start_ptr 指针向后移动一位，继续处理下一个活动的开始时间。
  
• 当 start_times[start_ptr] >= end_times[end_ptr] 时，说明有一个活动已经结束，有主持人可以空闲出来去主持新的活动，不必要新增主持人。此时将 end_ptr 指针向后移动一位，继续检查下一个活动的结束时间。
  

示例说明

假设我们有三个活动，其开始和结束时间分别为 [(1, 3), (2, 4), (3, 5)]，分离并排序后的开始时间数组为 [1, 2, 3]，结束时间数组为 [3, 4, 5]。

• 初始时，start_ptr = 0，end_ptr = 0，start_times[0] = 1，end_times[0] = 3，由于 1 < 3，以是必要新增一个主持人，start_ptr 加 1。
  
• 此时 start_ptr = 1，end_ptr = 0，start_times[1] = 2，end_times[0] = 3，由于 2 < 3，又必要新增一个主持人，start_ptr 加 1。
  
• 接着 start_ptr = 2，end_ptr = 0，start_times[2] = 3，end_times[0] = 3，由于 3 >= 3，说明有一个主持人空闲出来了，end_ptr 加 1。
  

在这个过程中，我们并不关心具体哪个开始时间对应哪个结束时间，只根据时间点的先后顺序来判定是否必要新增主持人，最终可以正确计算出最少必要的主持人数量。
贪婪算法回顾

这题要求用贪婪算法，这里简朴回顾一下。
定义回顾

贪婪算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致效果是全局最优的算法。贪婪算法必要问题具备贪婪选择性质，即通过局部最优选择能得到全局最优解。
代码中的贪婪策略

在这个活动安排求最少主持人数量的问题里，我们的目的是尽可能复用主持人，使得所需主持人数量最少。代码里采用的贪婪策略如下：

• 优先安排开始时间早的活动：把全部活动的开始时间和结束时间分别排序后，按照活动开始的先后顺序依次处理。这一做法是由于越早开始的活动越必要优先安排主持人，符合直观上的安排逻辑。
  
• 动态调整主持人数量：借助两个指针分别遍历开始时间数组和结束时间数组，在每一步比力当前活动的开始时间和已有活动的结束时间。
  
  
  
  • 若当前活动的开始时间早于某个正在进行活动的结束时间，说明此时没有空闲主持人，必要新增一个主持人，这是当前步骤下的最优选择，由于要保证这个新活动能够顺利开展。
    
  • 若当前活动的开始时间晚于或等于某个正在进行活动的结束时间，意味着有主持人可以在这个新活动开始时空闲出来，不必要新增主持人，这样就复用了已有的主持人资源，也是当前步骤下为淘汰总主持人数量做出的最优选择。
    
  
  

贪婪选择能得到全局最优解的缘故原由

在这个问题中，每一次对主持人数量的调整都是基于当前活动的开始和结束时间的比力，做出的是使当前所需主持人数量尽可能少的选择。由于活动的安排是按照时间顺序依次进行的，每一步的局部最优选择累积起来，最终得到的就是全局最少的主持人数量，以是该算法满足贪婪选择性质，属于贪婪算法。
方法二：看牛客官方题解

牛客题解链接

• 方法重载排序+大顶堆（扩展思路）
  
• 知识点：优先队列
  

优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，别的更小的元素在堆下方，小顶堆与其刚好相反。且由于容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是                                   O                         (                         l                         o                                   g                            2                                  n                         )                              O(log_2n)                  O(log2​n)，而每次取出堆顶元素都是直接取出。
具体做法：
step 1：重载sort函数，将开始时间早的活动放在前面，相同环境下再思量结束时间较早的。
step 2：利用小顶堆辅助，其中堆顶是还未结束的将要最快结束的活动的结束时间。
step 3：起首将int的最小数加入堆中，遍历每一个开始时间，如果堆顶的结束时间小于当前开始时间，可以将其弹出，说明少必要一个主持人。
step 4：除此之外，每次都必要将当前的结束时间必要加入堆中，代表必要一个主持人，最后遍历完成，堆中还有多少元素，就必要多少主持人。

Python代码实现

1. from queue import Queue, PriorityQueue
2. class Solution:
3.     #优先比较开始时间，再比较结束时间
4.     def comp(a:List[int], b: List[int]):
5.         if a[0] == b[0]:
6.             return a[1] - b[1]
7.         else:
8.             return a[0] - b[0]
9.         
10.     def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
11.         startEnd.sort(key = functools.cmp_to_key(Solution.comp))
12.         #小顶堆
13.         q = PriorityQueue()
14.         #可能有负区间
15.         q.put(-2147483648)
16.         for i in range(n):
17.             temp = q.get()
18.             #最近的活动结束时间小于当前活动开始时间
19.             if temp > startEnd[i][0]:  
20.                 q.put(temp)
21.             q.put(startEnd[i][1])
22.         #剩余的活动等于主持人数
23.         return q.qsize()

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。