2 solutions

  • 0
    @ 2025-10-20 17:12:40
    #include<bits/stdc++.h>
    using namespace std;
    struct PII{
    	int x,y;
    };
    bool cmp(PII a,PII b)
    {
    	if(a.y<b.y) return 1;
    	return 0;
    }
    int main()
    {
    	int n;
    	cin>>n;
    	vector<PII> v(n);
    	for(int i=0;i<n;i++)
    	{
    		cin>>v[i].x>>v[i].y;
    	}
    	sort(v.begin(),v.end(),cmp); //按照y从大到小排序
    	int res=1,ed=v[0].y;
    	for(int i=1;i<n;i++)
    	{
    		if(ed<v[i].x) //出现缝隙
    		{
    			res++;
    			ed=v[i].y; //选择当前区间最右边的点
    		}
    	}
    	cout<<res;
    	return 0;
    }
    
    • 0
      @ 2025-5-24 11:51:01
      #include<bits/stdc++.h>
      using namespace std;
      const int N=1e5+10;
      struct Node{ //定义一种结构体,按照区间右端点从小到大排序
          int l,r;
          bool operator<(const Node& W)
          {
              return r<W.r;
          }
      }range[N];
      int main()
      {
          int n;
          cin>>n;
          for(int i=1;i<=n;i++)
          {
              cin>>range[i].l>>range[i].r;
          }
          sort(range+1,range+1+n);
          int res=0,ed=-2e9;
          for(int i=1;i<=n;i++)
          {
              if(ed<range[i].l) //当前所选的点没有包含当前区间
              {
                  res++;//新选一个点
                  ed=range[i].r; //更新当前所选的点的坐标
              }
          }
          cout<<res;
          return 0;
      }
      • 1

      Information

      ID
      246
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      5
      Tags
      # Submissions
      39
      Accepted
      18
      Uploaded By