1.选点问题分析
问题描述
给定n个区间[ai,bi]，要求选择尽可能少的点，使得每个区间内至少包含一个点。即，找到最小点集P，使得对于任意区间[ai,bi]，存在p属于P满足ai<=p<=bi。
贪心策略
1.将所有区间按照右端点bi从小到大排序。如果右端点相同，则按左端点排序（左端点顺序不影响主要策略，但可保持一致）。
2.初始化点集P为空，并设一个变量last_point记录上一个选择的点的位置。
3.依次处理每个区间：
-如果当前区间[ai,bi]已经包含last_point（即ai<=last_point），则跳过该区间。
-否则，选择当前区间的右端点bi作为一个新点，将其加入P，并更新last_point=bi。
时间复杂度分析
-排序：O(nlogn)，其中n为区间数量。
-扫描：一次线性遍历，每次判断是否选点需要常数时间，共O(n)。
总时间复杂度为O(nlogn)。若区间已按右端点排序，则可优化到O(n)，但通常需要排序。
2.对贪心算法的理解
贪心算法是一种在每一步选择中都采取当前状态下最优（即局部最优）的决策，从而希望导致全局最优解的算法策略。它通常用于解决最优化问题，尤其是那些具有贪心选择性质和最优子结构的问题。
核心思想
贪心算法并不从整体最优上加以考虑，而是通过一系列局部最优选择来构造全局最优。每一步的选择都依赖于之前的选择，但不依赖于未来的选择，也不回退（无回溯）。
适用条件
1.贪心选择性质：问题的整体最优解可以通过一系列局部最优选择得到。即，每一步的贪心选择都是安全的，可以保证最终得到全局最优解。
2.最优子结构：问题的最优解包含其子问题的最优解。也就是说，通过子问题的最优解可以推导出原问题的最优解。
基本步骤
1.将问题分解为若干子问题。
2.定义贪心策略，确定每一步的选择标准。
3.根据贪心策略迭代做出选择，并缩小问题规模。
4.组合所有选择得到最终解。
优点与局限性
-优点：通常高效，时间复杂度低，易于实现和理解。
-局限性：并非所有问题都适用，贪心策略不一定能得到全局最优解。对于某些问题，需要证明贪心选择性质才能确保正确性。
典型应用
-活动选择问题
-霍夫曼编码
-最小生成树（Prim算法、Kruskal算法）
-单源最短路径（Dijkstra算法）
-区间调度和覆盖问题