1 solutions

  • -1
    @ 2025-6-7 9:42:57
    #include<bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> PII;
    #define l first
    #define r second
    const int N=1e5+10;
    PII q[N];
    int main()
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>q[i].l>>q[i].r;
        }
        sort(q,q+n); //按照区间左端点排序 
        priority_queue<int,vector<int>,greater<int> > heap; //小根堆 
        for(int i=0;i<n;i++)
        {
            if(heap.size()==0||heap.top()>=q[i].l) //组为空,或者是所有组的区间右端点都大于等于当前区间左端点 
            {
                heap.push(q[i].r); //新开一个 
            }
            else //在最小的后面加入当前区间 
            {
                heap.pop();
                heap.push(q[i].r);
            }
        }
        cout<<heap.size();
        return 0;
    }
    • 1

    Information

    ID
    249
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    17
    Accepted
    4
    Uploaded By