- 选点问题分析
问题描述
给定n个区间[lᵢ, rᵢ]，选择最少的点，使得每个区间至少包含一个点。
我的贪心策略
我采用按右端点排序的贪心策略：
算法步骤： - 将所有区间按右端点从小到大排序
- 初始化选择的点集为空，计数器count=0
- 遍历排序后的区间：
如果当前区间不包含任何已选择的点
则选择当前区间的右端点作为新点
计数器加1 - 返回计数器count
证明贪心选择性质
定义
设区间集S按右端点排序：r₁ ≤ r₂ ≤ ... ≤ rₙ
设OPT是最优解的点集
设ALG是按上述算法得到的点集
证明：
定理1（贪心选择性质）：存在一个最优解，其第一个点选择r₁。
证明：
设OPT是一个最优解，p₁是OPT中编号最小的点。 - 如果p₁ = r₁，定理成立
- 如果p₁ < r₁：
由于r₁是第一个区间的最右端点，区间[l₁, r₁]必须包含一个点
p₁在[l₁, r₁]中，且p₁ < r₁
将p₁替换为r₁，所有包含p₁的区间仍然被覆盖
得到的新解仍然是可行的，且点数不变 - 如果p₁ > r₁：
p₁不在区间[l₁, r₁]中，矛盾（因为OPT必须覆盖所有区间）
因此，存在最优解以r₁为第一个点。
定理2（最优子结构）：设S'是不被点r₁覆盖的剩余区间集合，则原问题的最优解包含子问题S'的最优解。
证明：
设原问题的最优解为OPT，包含点r₁。
删除所有包含r₁的区间后，剩余区间集为S'。
OPT中除r₁外的点构成S'的一个覆盖。
由于OPT是最优的，这些点也是S'的最优覆盖。
定理3（算法正确性）：通过数学归纳法
基础：当n=1时，选择r₁显然最优
归纳：假设对前k-1个区间算法最优
对前k个区间，算法选择r₁，然后递归解决S'
由定理1和2，这构成整体最优解
时间复杂度分析
设n为区间数量： - 排序阶段：O(n log n)
使用快速排序或归并排序 - 扫描阶段：O(n)
只需遍历一次排序后的区间 - 总时间复杂度：O(n log n)
排序是主要开销
空间复杂度：
O(n)：存储区间数据
O(1)：额外空间（不考虑输入存储） - 对贪心算法的理解
基本概念
贪心算法是一种局部最优导向全局最优的算法设计范式。它在每一步都做出在当前状态下看起来最好的选择，希望这样的局部最优选择能导致全局最优解。
核心特征 - 局部最优选择：每一步只考虑当前最优，不考虑长远影响
- 无后效性：一旦做出选择，不再改变
- 自顶向下：从初始问题出发，逐步做出选择
贪心算法的三要素 - 贪心选择性质
定义：所求问题的整体最优解可以通过一系列局部最优选择达到。
关键：可以通过贪心选择来构造最优解，且每一步的选择只依赖于之前的选择，不依赖于将来的选择。
证明方法：
交换论证：证明可以用贪心选择替换最优解中的选择
归纳法：数学归纳证明
拟阵理论：某些问题可形式化为拟阵贪心 - 最优子结构
定义：问题的最优解包含其子问题的最优解。
意义：保证了贪心选择的递归正确性。一旦做出贪心选择，剩余问题与原问题具有相同结构。 - 贪心策略
定义：确定每一步如何选择的具体规则。
常见策略：
最短路径：Dijkstra算法（选择当前距离最小的点）
最小生成树：Prim算法（选择连接树的最小边）
区间问题：按端点排序
哈夫曼编码：合并频率最小的节点
