算法第四章作业

include

include

include

using namespace std;

struct Interval {
int left;
int right;
};

int main() {
int n;
cin >> n;
vector intervals(n);
for (int i = 0; i < n; i++) {
cin >> intervals[i].left >> intervals[i].right;
}

sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
    return a.right < b.right;
});

int count = 0;
int last_point = -10000;

for (int i = 0; i < n; i++) {
    int cur_left = intervals[i].left;
    int cur_right = intervals[i].right;

    if (cur_left > last_point) {
        count++;
        last_point = cur_right;
    }
}

cout << count << endl;

return 0;

}
1.针对于这段代码来说他的贪心策略为区间按右端点升序和未被覆盖时选当前区间右端点，用最少的点覆盖最多区间。
证明：设最优解为规模最小的点集 O，贪心解为点集 G，排序后区间右端点满足 b₁≤b₂≤…≤bₙ。贪心解首个点 g₁=b₁，最优解首个点 o₁必≥b₁（否则无法覆盖首区间），将 o₁替换为 g₁后，O 仍合法且规模不变；以此类推，最优解中所有点均可替换为贪心解对应点，替换后仍为最优规模的合法解，故 G 规模与 O 相等；同时 G 能覆盖所有区间（未覆盖区间必选其右端点，后续区间右端点更大，确保覆盖），因此 G 是最优解。

2.排序的时间复杂度是 O(nlogn)输入遍历、贪心选点的时间复杂度是 O(n)，当 n 增大时（例如 n=10⁴、10⁵），nlogn 的增长速度会远快于 n，比如 n=10⁵时，nlogn 大约是 5×10⁵，而 n 本身仅为 10⁵，因此，代码的整体时间复杂度由排序操作的O(n log n)主导，其余环节的O(n)和O(1)时间消耗可忽略不计，最终代码的整体时间复杂度为O(n log n)。
2.我认为贪心算法是一种 “启发式算法”，它在解决问题时，通过一系列局部最优的选择（即 “贪心选择”），试图构造出全局最优解。其核心前提是：问题必须具备 “贪心选择性质” 和 “最优子结构性质”—— 这是贪心能得到全局最优解的关键，也是和 “盲目贪心” 的本质区别。就像有多个讲座时间段重叠，想参加最多讲座，策略是 “选结束时间最早的讲座”，这样能留出更多时间参加后续讲座，本质是 “每一步选‘占用时间成本最低’的选项”。核心逻辑是每一步都做出当下最优的选择，不回头、不后悔，最终期望得到全局最优解.且此算法的注意点为先验性质（贪心选择 + 最优子结构），再定策略（绑定目标 + 预处理），后证正确性（交换论证 / 归纳法），最后控实现（边界 + 测试）。其本质是 “精准找对局部最优的方向”，而非 “凭感觉选”。