区间问题

1.区间选点/最大不相交区间数量。
https://www.acwing.com/problem/content/907/
https://www.acwing.com/activity/content/problem/content/1112/
思路即按右区间端点大小对所有区间进行排序，然后找到最多相交的区间然后化为一组。
代码：

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    vector<pair<int,int>>a;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        a.push_back({x,y});
    }
    sort(a.begin(),a.end(),[&](auto&x,auto&y){
       return x.second<y.second; 
    });
    int res= 0;
    int last = -1e9-1;
    for(auto&p:a)
    {
        if(p.first>last)//如果遍历到的区间的左区间大于上一个区间的右区间，则需要新加一组。
        {
            res++;
            last =p.second;
        }
    }
    cout<<res<<endl;
}

2.区间分组。
https://www.acwing.com/problem/content/908/
找到最少的组，每组中区间两两不相交。
思路：对所有区间的左区间进行排序，然后依次加入右端点最小堆，若区间的左端点小于堆顶右端点的最小值，则区间相交不能合并。若大于右端点的最小值，则合并为一组，并更新该组的右端点的值为该区间的值。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N =1e5+5;
vector<pair<int,int>>p(N,pair<int,int>());
int main(void)
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        p[i].first =a;
        p[i].second =b;
    }
    sort(p.begin(),p.begin()+n,[&](pair<int,int>&a,pair<int,int>&b){
        return a.first<b.first;
    });
    auto cmp = [&](pair<int,int>&a,pair<int,int>b){
        return a.second>b.second;
    };
    priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)>pq(cmp);
    for(int i=0;i<n;i++)
    {
        if(pq.empty() ||  pq.top().second>=p[i].first) pq.push(p[i]);
        else
        {
            pq.pop();
            pq.push(p[i]);
        }
    }
    cout<<pq.size()<<endl;
    
    
}

3.区间覆盖
https://www.acwing.com/activity/content/problem/content/1114/
思路：对所有区间按左端点进行排序，遍历区间，找到右端点大于要覆盖区间[s,t]的区间，对[s,t]进行更新，最终判断是否能够覆盖。
代码：

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    int s,t;
    cin>>s>>t;
    int n;
    cin>>n;
    vector<pair<int,int>>p;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        p.push_back({a,b});
    }
    sort(p.begin(),p.end(),[&](auto&a,auto&b){
        return a.first<b.first;
    });
    int res=0;
    bool flag =false;
    for(int i=0;i<n;i++)
    {
        int j=i;
        int r=-2e9;
        while(j<n&&p[j].first<=s)//找到s左侧所有的区间。
        {
            r= max(r,p[j].second);//确定能延伸到右侧的最大值
            ++j;
        }
        if(r<s)//若最大值也不能超过s,那么无法被覆盖。
        {
            res =-1;
            break;
        }
        ++res;//使用能延伸到最右侧的最大值的区间
        if(r>=t)//若已经能覆盖完全，结束寻找
        {
            flag =true;
            break;
        }
        s=r;//更新左端点。
        i=j-1;//更新i
    }
    if(!flag) res=-1;
    cout<<res<<endl;
    
}

4.查询合并区间问题。
https://leetcode.cn/problems/range-module/
珂朵莉树。
代码：

class RangeModule {
public:
    map<int,int>mp; //[R,L]形式存储，方便查找
    RangeModule() {

    }
    
    void addRange(int left, int right) {
        int l = left;
        int r =right;
        auto p  =mp.lower_bound(left);//找到第一个右端点大于left 的区间
        while(p!=mp.end() && p->second<=r)
        {
            l = min(l,p->second);
            r = max(r,p->first);
            auto t =p;
            p++;
            mp.erase(t);
        } 
        mp[r]=l;
    }
    
    bool queryRange(int left, int right) {
        auto p = mp.lower_bound(left);
        if(p==mp.end()) return false;
        if(p->second<=left && p->first>= right) return true;
        return false; 
    }
    
    void removeRange(int left, int right) {
        auto p = mp.lower_bound(left+1);
        while(p!=mp.end() && p->second<=right)
        {
            if(p->second<left)
            {
                mp[left] = p->second;
            }
            if(p->first>right)
            {
                mp[ p->first] =right;
                break;
            }
            else 
            {
            auto t =p;
            p++;
            mp.erase(t);
            }
        }
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */