江门市网站建设_网站建设公司_展示型网站_seo优化
2025/12/16 23:50:03 网站建设 项目流程

一:选点问题
我的贪心策略:
1.将所有区间按照右端点right从小到大排序;
2.每次选择右端点最小的、且与已选区间不重叠的区间;

设排序后的第一个区间为[l1, r1](右端点最小);
设某个最优解为S,其中第一个选择的区间是[lk, rk];
由于r1 ≤ rk(第一个区间右端点最小),用[l1, r1]替换[lk, rk]:替换后区间数量不变;
[l1, r1]结束时间更早,为后续选择留出更多空间,替换后仍然是合法解(因为r1 ≤ rk,不会与后续区间冲突)
因此存在包含[l1, r1]的最优解

主要操作的时间复杂度:
1.输入数据:O(n)
2.排序:O(n log n)
3.贪心选择:O(n)
总时间复杂度 = O(n log n) + O(n) = O(n log n)

二:我对贪心算法的理解
贪心算法是一种基于局部最优选择来构建全局最优解的算法范式。它在每个决策点都做出当前看来最好的选择,而不考虑整体情况。通过推导每一个局部最优解来得出最终解。贪心算法高效简单,但是适用的问题不多。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询