文章目录
前言
一、贪心
二、例题，代码
AcWing 905. 区间选点
本题分析
AC代码
AcWing 908. 最大不相交区间数量
本题分析
AC代码
AcWing 906. 区间分组
本题分析
AC代码
AcWing 907. 区间覆盖
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：贪心——区间选点，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、贪心
贪心：利益最大化，即找到最优的情况，贪心问题难在证明，即你可能能推断出这个题目的正确解法，但是这个解法下为什么就是最优解不好证明。
区间问题其实就是区间的左右端点的排序问题
二、例题，代码
AcWing 905. 区间选点
本题链接：AcWing 905. 区间选点
本博客给出本题截图：
本题分析
把每一段区间按照右端点进行排序，然后开始依次遍历，res代表答案，ed是本区间的右端点，如果存在下一个区间的左端点大于本区间的右端点，那么证明这两个区间内没有交集，就让res ++;，然后把ed更新成下一个区间的右端点.
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 100010; struct St { int l, r; bool operator < (const St w) const { return r < w.r; } }st[N]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int l, r; scanf("%d%d", &l, &r); st[i] = {l, r}; } sort(st, st + n); int res = 0, ed = -1e9; for (int i = 0; i < n; i ++ ) if (st[i].l > ed) { res ++; ed = st[i].r; } printf("%d", res); return 0; }
AcWing 908. 最大不相交区间数量
本博客给出本题截图：
本题分析
本题与上题一致
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 100010; struct St { int l, r; bool operator < (const St w) const { return r < w.r; } }st[N]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int l, r; scanf("%d%d", &l, &r); st[i] = {l, r}; } sort(st, st + n); int res = 0, ed = -1e9; for (int i = 0; i < n; i ++ ) if (st[i].l > ed) { res ++; ed = st[i].r; } printf("%d", res); return 0; }
