给定 N 个闭区间[ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两######两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
区间分组问题
贪心解法 将区间按照左端点进行排序
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n;
struct node{
int l, r;
bool operator < (const node &w) const{
return l < w.l;
}
}a[N];
int main ()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++){
int l, r;
scanf("%d%d", &l, &r);
a[i] = {l, r};
}
sort(a, a + n);
priority_queue<int,vector<int>,greater<int>> heap;
for(int i = 0; i < n; i ++){
if(heap.empty() || heap.top() >= a[i].l) heap.push(a[i].r);
else{
heap.pop();
heap.push(a[i].r);
}
}
cout << heap.size() << endl;
return 0;
}
离散化 + 前缀和
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 200010;
vector<int> alls;
vector<PII> query;
int n;
long long s[N];
int find(int x){
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(alls[mid] <= x) l = mid;
else r = mid - 1;
}
return l + 1;
}
int main ()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++){
int l, r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for(auto x : query){
int l = find(x.first), r = find(x.second);
s[l] += 1, s[r + 1] -= 1;
}
long long res = 0;
for(int i = 1; i <= N; i ++){
s[i] += s[i - 1];
}
for(int i = 1; i <= N; i ++) res = max(res, s[i]);
cout << res << endl;
return 0;
}
区间覆盖 将区间按照左端点进行排序
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
输入格式
第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。
第二行包含整数 N，表示给定区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出 −1。
数据范围
1≤N≤105,
−109≤ai≤bi≤109,
−109≤s≤t≤109
输入样例：
1 5
3
-1 3
2 4
3 5
输出样例：
2
using namespace std;
int n;
const int N = 100010;
struct node
{
int l, r;
}q[N];
bool cmp(node a, node b)
{
return a.l < b.l;
}
int main ()
{
int st, ed;
scanf("%d%d",&st, &ed);
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
int l, r;
scanf("%d%d",&l, &r);
q[i] = {l,r};
}
sort(q,q+n,cmp);
int res = 0;
bool flag = false;
for(int i = 0; i < n; i++)
{
int j = i, r = -2e9;
while(j < n && q[j].l <= st)
{
r = max(r,q[j].r);
j++;
}
if(r < st)
{
flag = false;
break;
}
res++;
if(r >= ed)
{
flag = true;
break;
}
st = r;
i = j - 1;
}
if(!flag) res = -1;
cout << res << endl;
return 0;
}
区间选点问题 将区间按照右端点进行排序
给定 N 个闭区间[ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
struct node{
int l, r;
bool operator < (const node &w) const{
return r < w.r;
}
}a[N];
int main ()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++){
int l, r;
cin >> l >> r;
a[i] = {l, r};
}
sort(a, a + n);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i ++){
if(a[i].l > ed){
res ++;
ed = a[i].r;
}
}
cout << res << endl;
return 0;
}
区间最大不相交数量 将区间按照右端点进行排序
给定 N 个闭区间[ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互######不相交（包括端点）。
输出可选取区间的最大数量。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
using namespace std;
int n;
const int N = 100010;
struct node{
int l, r;
}q[N];
bool cmp(node a, node b)
{
return a.r < b.r;
}
int main ()
{
cin >> n;
for(int i = 0; i < n; i ++){
int l, r;
cin >> l >> r;
q[i] = {l, r};
}
sort(q, q + n, cmp);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i ++)
{
if(q[i].l > ed)
{
res ++;
ed = q[i].r;
}
}
cout << res << endl;
return 0;
}
