贪心算法-区间问题 C++

2024/11/29 22:42:15 来源：https://blog.csdn.net/m0_62112384/article/details/144009317 浏览: 次关键词：贪心算法-区间问题 C++

题目一

在这里插入图片描述

解题思路

原题解：https://www.acwing.com/solution/content/79913/ 在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;struct Range {int l, r;bool operator < (const Range &w) const {return r < w.r;}
}range[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ){scanf("%d%d", &range[i].l, &range[i].r);}sort(range, range + n);int res = 0, ed = -0x3f3f3f3f;for (int i = 0; i < n; i ++ ){if (ed < range[i].l){res ++;ed = range[i].r;}}cout << res;return 0;
}

题目二

在这里插入图片描述

解题思路

在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;struct Range {int l, r;bool operator < (const Range &w) const {return r < w.r;}
}range[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ){scanf("%d%d", &range[i].l, &range[i].r);}sort(range, range + n);int res = 0, ed = -0x3f3f3f3f;for (int i = 0; i < n; i ++ ){if (ed < range[i].l){ed = range[i].r;res ++;}}cout << res;return 0;
}

题目三

在这里插入图片描述

解题思路

原题解：https://www.acwing.com/solution/content/14773/
在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>
#include<queue>using namespace std;const int N = 1e5 + 10;struct Range {int l, r;bool operator < (const Range &w) const{return l < w.l;}
}range[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ){scanf("%d%d", &range[i].l, &range[i].r);}sort(range, range + n);priority_queue<int ,vector<int>, greater<int>> heap;for (int i = 0; i < n; i ++){if (heap.empty() || range[i].l <= heap.top()){heap.push(range[i].r);}else{heap.pop();heap.push(range[i].r);}}cout << heap.size();return 0;
}

题目四

在这里插入图片描述

解题思路

原题解：https://www.acwing.com/solution/content/16980/
在这里插入图片描述
为什么r = -2e9不能放在for循环内：
例如样例：
4 10 2
4 5
11 12
当第一轮st更新后是5，第二轮j 还是 0，不过此时应该退出了，但如果-2e9放在外面，
if (r < st)
{
res = -1;
break;
}
就不会执行

代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;struct Range {int l, r;bool operator < (const Range &w) const {return l < w.l;}
}range[N];int main()
{int st, ed, n;cin >> st >> ed >> n;for (int i = 0; i < n; i ++ ){scanf("%d%d", &range[i].l, &range[i].r);}sort(range, range + n);int res = 0;bool flag = false;for (int i = 0; i < n; i ++){int j = i, r = -0x3f3f3f3f;while (range[j].l <= st && j < n){r = max(r, range[j].r);j ++;}if (r < st){flag = true;break;}res ++;st = r;if (r >= ed){break;}i = j - 1;}if (flag || st < ed){res = -1;}cout << res;return 0;
}