区间相关问题

此类问题区间有左右两个端点，非常适合用 pair 容器，

选择不相关区间

选择最多不相关区间数，按右端点排序相同在按左端点排序（从小到大），

选择第一个区间后，排除相关区间，再重复选符合的第一个，直到不能选择

例 http://nyoj.top/problem/14

#include<iostream>//http://nyoj.top/problem/14
#include<algorithm>//不相交区间最大问题
using namespace std;
const int maxn = 1e5+100;
pair<int, int> a[maxn];
int main(){
    int n,m;cin >> m;
    while(m--){
        cin >> n;
        for(int i = 0; i < n; i++)cin>>a[i].second >> a[i].first;
        sort(a,a+n);
        int tmp = a[0].first;
        int cnt = 1;
        for(int i = 1; i < n; i++)
        {
            if(a[i].second > tmp)cnt++,tmp = a[i].first;
        }
        cout << cnt <<"
";
    }
    return 0;
}
/*
Sample Input
2
2
1 10
10 11
3
1 10
10 11
11 20

Sample Output
1
2
*/

View Code

区间选点问题

选择最小的点使所有区间都包含至少一个点，先按左端点排序，再按右端点排序（从小到大），，选择第一个区间右端点为基准，遍历若区间左端点大于基准，则点数++ 并更新基准为此区间的右端点，若区间右端点小于基准，则更新基准为此区间的右端点，纸上画个图就好懂了

例 //http://nyoj.top/problem/891

#include<iostream>//http://nyoj.top/problem/891
#include<algorithm>//求区间选最少点问题
using namespace std;

int main(){
    int n;
    pair<int ,int > a[110];
    while(cin>> n){
        for(int i = 0; i < n; i++)cin >> a[i].first >> a[i].second;
        sort(a,a+n);
        int tmp = a[0].second;
        int cnt = 1;
        for(int i = 0; i < n; i++)
        {
            if(a[i].first > tmp)cnt++,tmp = a[i].second;
            else if(a[i].second < tmp)tmp = a[i].second;
        }
        cout << cnt <<"
";
    }
    return 0;
}
/*
Sample Input
4
1 5
2 4
1 4
2 3
3
1 2
3 4
5 6
1
2 2
Sample Output
1
3
1
*/

View Code

区间覆盖问题

选择尽可能少的区间覆盖一条指定线段，先按区间左端点排序（从小到大），选择第一个区间的右端点为基准，遍历找当前左端点小于基准（以次保证连续）的区间中右端点最大的区间，然后将这个区间的右端点再作为基准重复上述操作 enmmmmmmmm

例 http://nyoj.top/problem/12

#include<iostream>//http://nyoj.top/problem/12
#include<algorithm>//求最小区间数覆盖问题
#include<cmath>
using namespace std;
const int maxn = 1e5+100;
pair<double,double> item[maxn];
double t,b,h,w;
int n,m;
int main(){
    cin >> m;
    while(m--)
    {
        cin >> n >> w >> h;
        h /= 2.0;int pose = 0,cnt = 0, lb = 0;
        for(int i = 0; i < n; i++){
            cin >> t >> b;
            if(b < h) continue;
            item[pose].first = t-sqrt(b*b-h*h);
            item[pose++].second = t+sqrt(b*b-h*h);
        }
        sort(item,item+pose);
        bool flag = false;
        int beg = 0, i;double maxv;
        if(item[0].first > 0){cout<<"0
";continue;}
        while(lb < w){    
            maxv = 0;
            for(i = beg; i<pose && item[i].first<=lb; i++)
                maxv = max(maxv, item[i].second);
            if(maxv > lb)cnt++,lb = maxv,beg = i;
            else {flag = true;break;}
        }
        if(flag)cout<< "0
";
        else    cout<< cnt << "
";
    }
    return 0;
}
/*
Sample input
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
Sample output
1
2
*/

View Code

https://vjudge.net/problem/POJ-1328
区间覆盖问题