2 solutions

  • 2
    @ 2026-1-2 14:10:20
    #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;
    }
    
    
    • -2
      @ 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
      58
      Accepted
      18
      Uploaded By