选点问题的贪心算法分析

1.请分析作业的"选点问题"，说明你的贪心策略，证明你的算法满足贪心选择性质，并给出时间复杂度分析
1.1贪心策略
将所有区间按区间终点 b 升序排列（代码中sortIntervals函数实现冒泡排序，核心逻辑是比较intervals[j].b和intervals[j+1].b，保证终点小的区间在前）。遍历排序后的区间，若当前区间不包含上一个选中的点，则选择当前区间的终点作为新点（代码中lastPoint = intervals[i].b），并计数 + 1。
1.2算法证明
设贪心解 G 中第一个选中的点是 g₁，最优解 S 中第一个选中的点是 s₁。由于第一个区间的终点是所有区间中最小的终点，g₁ ≤ s₁，否则s₁无法覆盖第一个区间。若 g₁ ≠ s₁，将 S 中的 s₁ 替换为 g₁，新的集合 S' 仍能覆盖所有被 S 覆盖的区间，且S'的点数与S相同，仍是最优解。每次将最优解中的点替换为贪心选择的终点，最终最优解会被调整为贪心解，且点数不变。
综上，贪心选择的 “选当前区间终点” 策略能得到最少点，满足贪心选择性质
1.3时间复杂度
冒泡排序的时间复杂度为 O(n^2)，其中外层循环i执行n-1次，内层循环j执行n-1-i次。时间复杂度为 O(n)。
2.你对贪心算法的理解
贪心算法是一种以局部最优追求全局最优的算法思想，核心是每一步都做出当前看起来最好的选择，具有最优子结构性质——问题的最优解包含其子问题的最优解。