一、选点问题的贪心算法分析
问题定义
给定直线上 n 个闭区间 [a1,b1],[a2,b2],...,[an,bn]，选择最少的点，使每个区间至少包含一个选定点。
-
贪心策略
排序：将所有区间按右端点从小到大排序。
选点：初始化选点 p=b1（排序后第一个区间的右端点），计数 count=1；遍历后续区间，若当前区间左端点 ai>p，则更新 p=bi，count+=1。
最终 count 即为最少选点数量。 -
贪心选择性质证明
贪心选择性质：全局最优解可通过局部最优选择（选当前未覆盖区间的最右端点）得到。设全局最优解为 S，点数为 k；贪心算法选出的第一个点为 p=b1。
假设 S 中第一个点为 p′=p，因区间按右端点排序，p′≤b1=p。
所有被 p′ 覆盖的区间，必然被 p 覆盖（若 ai≤p′≤p，则 ai≤p）。
因此，将 S 中的 p′ 替换为 p，得到新解 S′，点数仍为 k，是最优解。
递归地，对剩余未覆盖区间重复此选择，最终得到全局最优解。
故该算法满足贪心选择性质。 -
时间复杂度分析
排序阶段：使用比较排序算法，时间复杂度 O(nlogn)。
遍历选点阶段：线性扫描所有区间，时间复杂度 O(n)。
总时间复杂度：O(nlogn)（排序为时间主导项）。
二、对贪心算法的理解
核心思想：每一步都做出局部最优的选择，不回溯、不考虑全局影响，通过一系列局部最优推导全局最优解。
关键前提贪心选择性质：全局最优解包含局部最优选择，是贪心算法正确性的核心保障。最优子结构性质：问题的全局最优解包含其子问题的最优解。
特点优点：思路简洁、代码实现简单、时间与空间复杂度低。缺点：适用范围窄，仅能解决满足贪心选择性质的问题；正确性需严格数学证明。
与其他算法的区别与动态规划：均需最优子结构；贪心自顶向下做局部选择，动态规划自底向上求解子问题并利用重叠子问题优化。与回溯：贪心无回溯过程，效率高；回溯枚举所有可能，适用于小规模问题。
典型应用：活动选择、哈夫曼编码、最小生成树（Kruskal/Prim）、单源最短路径（Dijkstra）。