[codeforces_597B] Restaurant(贪心)

题目链接

http://codeforces.com/problemset/problem/597/B

题意

输入：区间数目n、及n个区间的起止(左闭右闭)。

输出：最多不重叠的区间有多少个。

思路

贪心，最早结束优先。

其他

1 贪心就要彻底一点，多余的处理通常没用。

2 此题还涉及sort排序。

代码

#include<math.h>

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;

bool finishEarly(pair<int,int> &order1,pair<int,int> &order2){

    return order1.second<order2.second;

}

int main(int argc, const char * argv[]) {

    int n;

    scanf("%d",&n);

    vector<pair<int, int>> orderVec;

    while(n--){

        int l,r;

        scanf("%d %d",&l,&r);

        orderVec.push_back(make_pair(l, r));

    }

    sort(orderVec.begin(), orderVec.end(),  finishEarly);

    int cnt=0;

    int end;

    for(vector<pair<int, int>>::iterator iter=orderVec.begin();iter!=orderVec.end();iter++){

        if(iter==orderVec.begin()){

            cnt++;

            end=iter->second;

        }

        else{

            if(iter->first>end){

                cnt++;

                end=iter->second;

            }

        }

    }

    printf("%d",cnt);

    return 0;

}

巴特西

[codeforces_597B] Restaurant(贪心)

题目链接

题意

思路

其他

代码

最新文章

热门文章