8 solutions

  • 0
    @ 2021-10-16 13:32:19

    这道题首先我们要得到最多能够开展多少活动,我的想法是将每个活动的时间以右边界为标准,按升序来排序,根据贪心的思想,我肯定得优先选择右边界最小的,然后从右边界最小的里面来匹配,看此时他的左边界是否符合要求,并且计数
    不多说 来看代码:

    #include <bits/stdc++.h>
    using namespace std;
    pair<int,int>pa[1005];
    bool cmp(pair<int,int>a,pair<int,int>b)
    {
    	return a.second<b.second;
    }
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;++i)
    	{
    		cin>>pa[i].first>>pa[i].second;
    	}
    	sort(pa+1,pa+n+1,cmp);
    	int cnt = 1;
    	int r = pa[1].second;//先确定最小的右边界
    	for(int i=1;i<=n;++i)
    	{
    		if(pa[i].first>=r){
    			cnt++;
    			r=pa[i].second;//每次匹配成功,将cnt++并且更新新的右边界
    		}
    	}
    	cout << cnt << endl;
    }
    

    Information

    ID
    91
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    6
    Tags
    # Submissions
    177
    Accepted
    56
    Uploaded By