区间问题
01.区间选点
题目描述
给定 N 个闭区间 [a_i,b_i]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 a_i,b_i，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1le Nle 10^5,−10^9le a_ile b_ile 10^9
输入样例：
代码语言：javascript复制3
-1 1
2 4
3 5输出样例：
代码语言：javascript复制2题解
时间复杂度
O(nlogn)
证明:
- 证明
ans$$le$$cnt：cnt是一种可行方案，ans是可行方案的最优解，也就是最小值。 - 证明
ans$$ge$$cnt：cnt可行方案是一个区间集合，区间从小到大排序，两两之间不相交。
所以覆盖每一个区间至少需要cnt个点。
核心思想
- 将每个区间按照右端点从小到大进行排序
- 从前往后枚举区间，end值初始化为无穷小
- 如果本次区间不能覆盖掉上次区间的右端点，
ed < range[i].l - 说明需要选择一个新的点，
res;ed = range[i].r;
- 如果本次区间不能覆盖掉上次区间的右端点，
核心函数
代码语言：javascript复制sort(nodes, nodes n);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i )
if(nodes[i].l > ed)
{
res ;
ed = nodes[i].r;
}代码实现
代码语言：javascript复制/**********************************************
* 她的店里只卖樱花 *
***********************************************/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <queue>
using namespace std;
#define fi first
#define se second
#define _for(i,b) for(int i=(0);i<(b);i )
#define rep(i,a,b) for(int i=(a);i<=(b);i )
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define ios_op cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define endl 'n'
#define sendl " n"
typedef priority_queue<int, vector<int>, greater<int> > PQ;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int Inf = 0x3f3f3f3f, Null = 0x80808080;
const double eps=1e-6;
const double PI=acos(-1.0);
const int MOD = 1e9 7;
const int N = 100010;
int n;
struct Node{
int l, r;
bool operator< (const Node& w)const{
return r < w.r;
}
}nodes[N];
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 (s ^ 48), s = getchar();
x *= f;
}
template <typename T> void print(T x) {
if (x < 0) { putchar('-'); print(x); return ; }
if (x >= 10) print(x / 10);
putchar((x % 10) '0');
}
int main (){
cin >> n;
for(int i = 0; i < n; i )
{
int l, r;
cin >> l >> r;
nodes[i] = {l, r};
}
sort(nodes, nodes n);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i )
if(nodes[i].l > ed)
{
res ;
ed = nodes[i].r;
}
cout << res << endl;
return 0;
}
