如何计算完成全部任务的最少容器数?现有heapq调度代码输出异常
问题根源拆解
你遇到的问题并非最初怀疑的判断逻辑错误,核心是两个隐蔽的逻辑漏洞:
1. 生成的room号是无效的动态值
当前代码offer函数最后返回的len(heap),本质是当前时刻正在运行的任务总数,根本不是固定绑定的容器ID。
顺着你代码的实际运行流程算一遍就能发现问题:
- 处理第一个任务
[0,12]:堆为空,push12,堆长1,返回room=1 - 处理第二个任务
[0,708]:堆顶12 > 0,不触发弹出,push708,堆长2,返回room=2 - 处理第三个任务
[108,156]:堆顶12 <=108,弹出12,此时堆长1,再push156,堆长回到2,返回room=2
这里正在运行的[0,708]任务和刚分配的[108,156]任务完全并行,本该在两个独立容器里运行,但因为返回值是动态堆长度,两个任务被打上了同一个room2的标签。
后续处理[156,168]时,弹出156、push168,堆长依然是2,继续返回room=2,所以你看到[0,708]和[156,168]同属room2,误以为是判断逻辑没拦住容器复用,实际上是返回的room号从一开始就没有跟踪真实的容器身份。
2. 最小堆的存储结构不完整
你怀疑的代码行while heap and heap[0] <= begin:本身是完全正确的判断逻辑——它的作用是找到最早结束的容器,只要容器结束时间 <= 当前任务开始时间,就说明容器空闲可复用。
但问题是你只把容器的结束时间存在堆里,根本没记录这个时间对应的容器编号。当容器空闲被复用时,你没法把这个空闲容器的ID分配给新任务,只能拿动态变化的堆长度凑数,自然会出现标签重复的问题。
正确的修改方向
把堆的存储结构从单独的“结束时间”改成(结束时间, 容器ID)的元组,跟踪每个堆元素对应的真实容器编号:
- 遇到空闲的堆顶元素,直接复用它的容器ID,更新结束时间后放回堆
- 如果没有空闲容器,就新分配一个ID(值为当前已使用的容器总数+1),把新的结束时间和新ID放进堆
这样生成的room号是固定绑定容器的,不会出现并行任务被分到同号的问题。核心修改逻辑参考:
import heapq def schedule(tasks): # 堆结构: (容器结束时间, 容器ID) heap = [] used_room_count = 0 def offer(begin, end): nonlocal used_room_count idle_rooms = [] # 弹出所有已空闲的容器 while heap and heap[0][0] <= begin: _, room_id = heapq.heappop(heap) idle_rooms.append(room_id) # 有空闲就复用,没有就新开容器 if idle_rooms: room_id = idle_rooms[0] else: used_room_count += 1 room_id = used_room_count heapq.heappush(heap, (end, room_id)) return room_id # 先按开始时间升序排序,开始时间相同按结束时间升序 sorted_tasks = sorted(tasks, key=lambda x: (x[0], x[1])) return ((offer(begin, end), (begin, end)) for begin, end in sorted_tasks)
额外注意的小坑
你贴的代码输出里所有时间都是字符串格式(比如('0', '12')),字符串比较会出现逻辑错误——比如字符串规则下'156' < '2',会直接打乱排序和判断逻辑,运行时要确保传入的时间值是数字类型,不是字符串。
内容的提问来源于stack exchange,提问作者craig3656
相关产品推荐
相关产品推荐

