基于最短时长贪心算法的无冲突事件调度问题求助

你当前的代码问题在于：仅按事件时长排序无法保证选出最多的无冲突事件。要实现“一天内调度尽可能多无冲突事件”的目标，经典的贪心策略是按事件结束时间升序排序——选择最早结束的事件，能为后续留出更多时间安排其他事件，这是经过证明的最优策略。

你的代码核心调度逻辑（遍历排序后的事件，选择不冲突的）是正确的，但排序规则错误，导致无法得到最优结果。

修正后的代码 #

def max_non_conflicting_events(events):
    # 按结束时间升序排序，这是选最多无冲突事件的关键
    events.sort(key=lambda x: x[1])
    finish_time = 0
    selected_events = []
    for event in events:
        start, end = event
        if start >= finish_time:
            selected_events.append(event)
            finish_time = end
    return selected_events

events = [(420, 480), (420, 510), (450, 550), (480, 570), (510, 540), (540, 570), (540, 630), (570, 630)]

print("原事件列表:", events)
print("最多无冲突事件:", max_non_conflicting_events(events))

输出结果 #

原事件列表: [(420, 480), (420, 510), (450, 550), (480, 570), (510, 540), (540, 570), (540, 630), (570, 630)]
最多无冲突事件: [(420, 480), (510, 540), (540, 570), (570, 630)]

为什么原策略不行？ #

按时长排序可能会选中结束时间较晚的短时事件，挤占后续更多事件的调度空间。比如你原代码会先选(510,540)（时长30），但如果先选(420,480)（时长60），后续还能再选3个事件，总数量更多。

如果你的需求确实是“优先选短时事件，即使总数不是最多”，那需要调整逻辑，但要明确：这种策略无法保证事件数量最大化。

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