← 返回编程题库
coding-min-rooms-for-streaming-jobs简单免费版2000ms未尝试

并发流式执行机的最小数量

Minimum Concurrent Streaming Jobs for Execution Windows

开始编码

执行平台组要为明天一批待处理的流式任务预分配「执行机」(rooms)。每个作业的执行窗口写作 [start, end)——半开区间,意味着一个作业在 t = 5 结束的同一刻另一个作业可以接着在 t = 5 开工、共用同一台机器。机器资源是稀缺的,所以团队想知道:要让每个作业都能在自己声明的窗口内运行、且任意时刻同一台机器上不会同时跑两个作业,至少需要多少台执行机?

请实现 solution(jobs: list[list[int]]) -> intjobs[k] = [start, end] 是第 k 个作业的整数刻度执行窗口,返回所需的最少执行机数。

示例solution([[0, 30], [5, 10], [15, 20]]) 返回 2——长作业 [0, 30) 占满 A 机;B 机依次跑 [5, 10)[15, 20)solution([[1, 5], [5, 10], [10, 15]]) 返回 1——三段窗口首尾恰好相接,按半开语义不算重叠,一台机器就能串起全部三个作业。solution([[1, 10], [2, 9], [3, 8], [4, 7]]) 返回 4——在 t = 4 时四个作业同时在跑,必须有 4 台执行机。

经典的两种 O(n log n) 解法都很标准:(a) 扫描线——每个作业转成一个 +1 起始事件和一个 −1 结束事件,按时间排序、相同时间先处理 −1(这是半开区间的合同),扫一遍维护 active 计数,取过程中的峰值;(b) 双指针——把 startend 分别排序,当 starts[i] < ends[j] 时推进 start 指针并 active += 1,否则推进 end 指针并 active -= 1。严格不等号 < 就是半开语义:相等时先释放后占用,峰值不增。退化作业 start == end 占用时长为 0,过滤掉或者依赖严格不等号即可,不影响答案。

约束条件

  • 0 ≤ len(jobs) ≤ 10⁴
  • 每个元素是长度为 2 的列表 [start, end],满足 0 ≤ start ≤ end ≤ 10⁹(整数)
  • 半开语义:`[1, 5)` 与 `[5, 10)` 不冲突(执行机在 t = 5 时刚好释放给下一个作业)
  • `start == end` 的退化作业为「瞬时作业」,占用时间为 0,所需执行机数也为 0
  • 返回所需并发执行机数(整数)

样例

Case 1 · empty schedule

输入: [[]]

期望: 0

没有任何作业,所需流式执行机为 0。

Case 2 · single job

输入: [[[1,5]]]

期望: 1

只有一个作业,需要 1 台执行机。

Case 3 · all disjoint — one room suffices

输入: [[[1,2],[3,4],[5,6]]]

期望: 1

三段窗口完全不重叠,可以串行复用同一台执行机。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · empty schedule

输入: [[]]

期望: 0

没有任何作业,所需流式执行机为 0。

Case 2 · single job

输入: [[[1,5]]]

期望: 1

只有一个作业,需要 1 台执行机。

Case 3 · all disjoint — one room suffices

输入: [[[1,2],[3,4],[5,6]]]

期望: 1

三段窗口完全不重叠,可以串行复用同一台执行机。