AcWing 906. 区间分组
本题链接：AcWing 906. 区间分组
本博客给出本题截图：
本题分析
按照左端点从小到大进行排序，如果存在本区间的右端点大于等于下一区间的左端点的话，意思就是两个区间有交集，那么就让答案 + 1，这里，我们用堆来模拟这个过程，堆（优先队列）（STL）见博客：（先鸽），手写堆见博客：（先鸽），我们堆中的元素存的是区间的右端点，这里我们用小根堆，即堆顶元素是右端点的最小值，如果堆为空或者堆顶元素要大于等于下一个区间的左端点，那么就要开一个新的组，把该区间的右端点放入堆中，反之即堆顶元素要小于下一个区间的左端点，那么就意味着，堆顶元素可以和该区间放入一个组中，因为我们要存储每一个组中的右端点的最大值作为该组的右端点，且堆顶元素小于下一区间的左端点，即堆顶元素小于下一区间的右端点，我们要存最大右端点，且这俩区间为一组，就弹出堆顶元素，然后把下一区间的右端点加入堆中.
AC代码
#include <cstdio> #include <algorithm> #include <queue> using namespace std; const int N = 100010; struct St { int l, r; bool operator < (const St w) const { return l < w.l; } }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); priority_queue <int, vector<int>, greater<int>> heap; for (int i = 0; i < n; i ++ ) { auto t = st[i]; if (heap.empty() || heap.top() >= t.l) heap.push(t.r); else { heap.pop(); heap.push(t.r); } } printf("%d", heap.size()); return 0; }
AcWing 907. 区间覆盖
本题链接：AcWing 907. 区间覆盖
本博客给出本题截图：
本题分析
先按照左端点从小到大进行排序。如何获得本题的最优解：st代表还未更新定线段区间的左端点，我们的核心目的就是在左端点i都小于st的情况下，选择右端点最大的区间
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 100010; struct Range { int l, r; bool operator < (const Range w) const { return l < w.l; } }range[N]; int main() { int st, ed; scanf("%d%d", &st, &ed); int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) { int l, r; scanf("%d%d", &l, &r); range[i] = {l, r}; } sort(range, range + n); bool success = false; int res = 0; for (int i = 0; i < n; i ++ ) { int j = i, r = -1e9; while (j < n && range[j].l <= st) { r = max(r, range[j].r); j ++; } res ++; if (r < st) break; if (r >= ed) { success = true; break; } st = r; i = j - 1; } if (!success) printf("-1"); else printf("%d", res); return 0; }
三、时间复杂度
关于贪心——区间选点的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
