1."选点"问题
（1）贪心策略：
按区间右端点从小到大排序，每次都选择当前区间的右端点作为点，以覆盖尽可能多的后续区间。
（2）证明贪心选择性质：
假设我们按右端点排序得到区间 𝐼1,𝐼2,…,𝐼𝑛（其中 𝐼1 右端点最小）。假设：存在一个最优解 OPT不包含 𝐼1 的右端点 𝑏1。 设 OPT 中覆盖 𝐼1 的点是 𝑝（必有 𝑎1≤𝑝≤𝑏1）。
构造新解：将 OPT 中的点 𝑝替换为 𝑏1 得到 OPT′。 𝑏1 仍覆盖 𝐼1（因为 𝑏1∈[𝑎1,𝑏1]）。对于 OPT 中其他原本被 𝑝 覆盖的区间 𝐼𝑗： 由于 𝑏1 是 当前所有未处理区间中右端点最小的，且 𝑝≤𝑏1 若 𝐼𝑗 被 𝑝 覆盖，则 𝑎𝑗≤𝑝≤𝑏𝑗 。 又因为区间按右端点排序，有 𝑏1≤𝑏𝑗 所以 𝑎𝑗≤𝑝≤𝑏1≤𝑏𝑗 ⇒ 𝑏1∈[𝑎𝑗,𝑏𝑗] 因此 𝑏1 也能覆盖 𝐼𝑗 。
矛盾：OPT′ 使用相同数量的点覆盖所有区间，且包含 𝑏1，这与“不存在包含 𝑏1 的最优解”的假设矛盾。
故存在一个最优解包含 𝑏1，贪心选择正确。
2.对贪心算法的理解
贪心算法在每个决策点都做出当前看起来最优的选择，希望这些局部最优选择能最终导致全局最优解。
关键特征：贪心选择性质：每一步的选择都是不可撤回的，当前选择不受未来选择影响。 最优子结构性质：问题的最优解包含子问题的最优解，做出贪心选择后，剩余问题仍然是相同类型的子问题。
贪心算法是局部最优解，是否是全局最优解要通过反证+替换的方法进行证明。