贪心五种常见模型 | FFY's Blog

---

1. 区间不相交问题

• 按右端点排序
• 枚举,当左端点未被标记时,$ans++$,标记右端点

---

2. 区间选点问题

• 按右端点排序
• 枚举,当该区间未被选够点时,从后往前选择未被选择的点,直到选够

---

3. 区间覆盖问题

• 按左端点排序
• 枚举,选择能覆盖当前节点,右端点最远的节点,将当前节点更新为该最远节点的右端点

---

4. 流水作业调度问题

• Johnson算法(比较迷,反正我没懂)
• 按$min(i.a,j.b)<min(i.b,j.a)$排序
• 枚举记录$ans$

---

5. 带限期和罚款的单位时间任务调度

• 按期限排序
• 用优先队列维护
• 若当前时间完成的任务数少于该时间能完成的任务数,直接将权值入队
• 若已经相等,取出队列中最小的元素与当前权值比较,将较大的入队
• 最后累加队列中的元素权值