贪心
区间选点
给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。位于区间端点上的点也算作区间内。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range{
int l,r;
bool operator< (const Range &w)const{
return r < w.r;
}
}range[N];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
range[i] = {l,r};
}
sort(range, range + n);
int res = 0, ed = -2e9;
for(int i=0;i<n;i++)
if(range[i].l > ed){
res++;
ed = range[i].r;
}
printf("%d\n",res);
return 0;
}
最大不相交区间数量
给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range{
int l,r;
bool operator< (const Range &w)const{
return r < w.r;
}
}range[N];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
range[i] = {l,r};
}
sort(range, range + n);
int res = 0, ed = -2e9;
for(int i=0;i<n;i++)
if(range[i].l > ed){
res++;
ed = range[i].r;
}
printf("%d\n",res);
return 0;
}
区间分组
给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。输出最小组数。
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;
const int N = 100100;
int n;
struct Range{
int l,r;
bool operator< (const Range &w) const{
return l < w.l;
}
}range[N];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
range[i] = {l,r};
}
sort(range, range + n);
priority_queue<int, vector<int>, greater<int>> heap;
for(int i=0;i<n;i++){
if(heap.empty() || heap.top() >= range[i].l){
heap.push(range[i].r);
}
else{
heap.pop();
heap.push(range[i].r);
}
}
printf("%d\n", heap.size());
return 0;
}
区间覆盖
给定 N 个区间 [ai,bi] 以及一个区间 [s,t]，请你选择尽量少的区间，将指定区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
思路：
1.将所有区间按照左端点从小到大进行排序
2.从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点的最大值
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100010;
int s,t;
int n;
struct Range{
int l,r;
bool operator< (const Range &w)const{
return l < w.l;
}
}range[N];
int main(){
scanf("%d%d",&s,&t);
scanf("%d",&n);
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
range[i]={l,r};
}
sort(range, range + n);
int ans = 0;
bool win = false;
for(int i=0;i<n;i++){
int j=i, r = -2e9;
while(j < n && range[j].l <= s){
r = max(r, range[j].r);
j++;
}
if(r < s){
ans = -1;
break;
}
ans++;
if(r >= t){
win = true;
break;
}
s = r;
i = j - 1;
}
if(!win) ans = -1;
printf("%d\n",ans);
return 0;
}
