1. 区间问题
1.1 区间选点
给定 N个闭区间 ,请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
struct node
{
int l, r;
bool operator < (const node &W) const
{
return r < W.r;
}
} arr[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i].l >> arr[i].r;
//按右端点从小到大排序
sort(arr + 1, arr + 1 + n);
int ans = 0;
int R = -2e9; //R表示上一连续区间的最右端的点
for (int i = 1; i <= n; i++)
{
if (arr[i].l > R) //如果不能覆盖掉右端点,则点数+1,更新右端点
{
ans++;
R = arr[i].r;
}
}
cout << ans << endl;
return 0;
}
2024年7月1日大约 3 分钟