最大CPU负载问题：集合替代堆的解法哪种更适配技术面试？

题目描述 #

给定一组作业列表Jobs，每个作业包含开始时间Start、结束时间End、运行时占用的CPU负载，所有作业运行在同一台机器上，要求计算任意时刻的最大CPU负载。

题目示例 #

示例1 #

• 输入Jobs：[[1,3,3], [2,5,4], [7,9,6]]
• 输出：7
• 解释：[1,4,3]和[2,5,4]两个作业时间重叠，二者同时运行的时间段(2,4)内总CPU负载为3+4=7，为最大值。

示例2 #

• 输入Jobs：[[6,7,10], [2,4,11], [8,12,15]]
• 输出：15
• 解释：所有作业均无时间重叠，因此取单个作业的最大负载15即可。

示例3 #

• 输入Jobs：[[1,4,2], [2,4,1], [3,6,5]]
• 输出：8
• 解释：时间区间[3,4]内三个作业同时运行，总CPU负载为8，为最大值。

两种实现方案 #

参考解法（最小堆实现） #

注：原参考代码存在缩进错误，return语句被误放在for循环内部、堆弹出语句后多了冗余逗号，下述代码已修正问题

from heapq import heappush, heappop

class job:
    def __init__(self, start, end, cpu_load):
        self.start = start
        self.end = end
        self.cpu_load = cpu_load

    def __lt__(self, other):
        # 按作业结束时间排序的最小堆
        return self.end < other.end

def find_max_cpu_load(jobs):
    # 按作业开始时间排序
    jobs.sort(key=lambda x: x.start)
    max_cpu_load, current_cpu_load = 0, 0
    min_heap = []
    
    for j in jobs:
        # 移除所有已经结束的作业
        while(len(min_heap) > 0 and j.start >= min_heap[0].end):
            current_cpu_load -= min_heap[0].cpu_load
            heappop(min_heap)
        # 将当前作业加入最小堆
        heappush(min_heap, j) 
        current_cpu_load += j.cpu_load
        max_cpu_load = max(max_cpu_load, current_cpu_load) 
    return max_cpu_load

个人实现（集合实现） #

class job:
    def __init__(self, start, end, cpu_load):
        self.start = start
        self.end = end
        self.cpu_load = cpu_load

def find_max_cpu_load(jobs):
    all_vals = set()
    jobs.sort(key=lambda x: x.start)
    currmax = 0

    for j in range(len(jobs) - 1): 
        all_vals.add(jobs[j].cpu_load)
        if jobs[j+1].start <= jobs[j].end:
            currmax = jobs[j].cpu_load
        upper = min(jobs[j].end, jobs[j+1].end)
        while jobs[j+1].start <= upper:
            currmax += jobs[j + 1].cpu_load
            if j < len(jobs) - 1:
                j += 1
            if j == len(jobs) - 1:
                break
        all_vals.add(currmax) 

    all_vals.add(jobs[len(jobs) - 1].cpu_load)
    return max(all_vals)

方案对比与面试建议 #

现有方案的问题 #

首先你的集合实现存在明显逻辑漏洞，无法通过所有测试用例：

• 内层while循环直接修改外层for循环的遍历变量j，会导致部分作业被跳过，遇到多个非连续重叠的作业时计算结果直接出错。
• 重叠判断逻辑只比较相邻两个作业的结束时间，没有处理「早开始的作业先结束、后续作业仅和部分运行中作业重叠」的场景，比如输入[[1,10,2], [2,3,1], [4,5,1]]就会算出错误结果。
• 用set存储负载值本身没有实际意义，反而增加了不必要的操作。

复杂度与适用性对比 #

• 修正后的堆解法是这类区间重叠问题的标准最优解：按作业开始时间排序耗时O(nlogn)，每个作业只会入堆、出堆各一次，单次堆操作耗时O(logn)，整体时间复杂度稳定在O(nlogn)，空间复杂度最坏为O(n)（所有作业全部重叠），可以覆盖所有复杂重叠场景，逻辑严谨可扩展。
• 你的集合实现就算修正逻辑漏洞，本质还是靠遍历相邻作业判断重叠，遇到多层重叠、作业结束时间错落的场景，时间复杂度会退化到O(n²)，不是最优解法。

你觉得堆没必要，本质是没考虑到复杂重叠场景下的负载增减需求：当新作业到来时，需要快速找出所有已经结束的作业，把它们的负载从当前总负载里减掉，最小堆可以O(1)拿到最早结束的作业，批量完成剔除操作，不需要遍历所有运行中的作业，效率优势非常明显。

面试选择建议 #

技术面试中这类题的评分优先级是：正确性 > 时间/空间复杂度最优 > 思路清晰易解释。排序+最小堆的思路是区间调度类问题的通用框架，不光能解决这道题，还能直接套用到最少会议室数、最多重叠区间数等一系列变种题，给出这个解法，面试官一眼就能判断你掌握了这类题的核心思路，也能体现你对堆数据结构应用场景的理解，是绝对的首选。
不建议使用你写的集合版本，首先存在逻辑硬伤，就算临时修好，也不是最优复杂度，思路也不具备通用性，很难拿到高分。建议吃透堆解法的思路，这属于面试高频考点，性价比很高。

内容的提问来源于stack exchange，提问作者confusedgeek