贪心

贪心算法是一种在每一步选择中都采取当前状态下最优决策的策略。它期望通过一系列局部最优选择，最终导向一个全局最优解。其核心在于“活在当下”，只考虑眼前利益，而无需瞻前顾后。

排序-选择类

• 场景：从一组元素中按某关键字挑选“尽可能好”的若干个或确定顺序。
• 常见做法：按关键字排序后线性扫描；若关键字随过程变化，可以用堆维护“当前最优候选”。
• 用途：选最大/最小若干项、最少/最多操作次数、最优排列顺序等。

---

带限制的贪心

• 场景：局部最优解不是直接选择最小值或者最大值。需要根据题目需求来确定如何确定我们的局部最优解法取决于什么数据。
• 常见做法：观察题目性质，寻找真正需要去贪心的内容来进行求解。

---

区间类（选取 / 覆盖 / 去重叠）

• 场景：区间选取最多不相交、用最少点/区间覆盖、删除最少区间消冲突等。
• 常见做法：按右端点升序选取；覆盖问题常按右端点推进；需要计数时配合扫描线/差分。
• 用途：活动安排、教室/会议室分配、摄像头/路灯最少放置等。

【思维导图】

【题目知识点分类】