贪心算法-区间问题 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;
}