知识卡片

普通读书笔记卡 · 3624.a.1.b.1.b

迭代选活动只查最后结束项

理解等级:中级

活动按结束时间排序后,迭代算法保留最近选中活动的结束时间;新活动只要开始不早于它,就与已选的全部活动兼容,因为已选活动中它结束最晚。

这样每个候选只检查一次,排序后的选择阶段为线性时间。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第15章 贪心算法 · 查看原书依据

      To see whether activity am is compatible with every activity currently in A, it suffices by equation (15.3) to check (in line 4) that its start time sm is not earlier than the finish time fk of the activity most recently added to A.

    参考来源

    - 位置:《算法导论(第4版)》第 15 章《贪心算法》(`OEBPS/chapter015.xhtml`,文本字符 [15000, 20000))。 - 结论依据:原文直接给出迭代选择器的单项兼容检验与最后结束时间不变量。 - 原始内容:To see whether activity a m is compatible with every activity currently in A , it suffices by equation (15.3) to check (in line 4) that its start time s m is not earlier than the finish time f k of the activity most recently added to A .