首页 > 代码库 > 【贪心】洛谷P1803 凌乱的yyy

【贪心】洛谷P1803 凌乱的yyy

https://www.luogu.org/problem/show?pid=1803 链接

这是一道裸的区间问题,和白书2.2.2节完全匹配。那就不啰嗦,直接上代码了。

代码实现

//本题要遵循的原则是 每次都选取结束最早的工作  #include <iostream>#include <algorithm>using namespace std;pair<int ,int> gongzuo[1000001];int n;int main(){    cin>>n;    for(int i=0;i<n;i++){        cin>>gongzuo[i].second; //注意这里把开始读做二的原因是 排序要拿first排序        cin>>gongzuo[i].first; // 把结束时间当做  first读入 因为等会要排序    }    sort(gongzuo , gongzuo + n);//这里的排序是以first为基准的    int ans=0,t=0;    for(int i=0;i < n ;i++){  //t是最后所选工作的时间        if(t <= gongzuo[i].second){            ans++;            t = gongzuo[i].first;        }    }    cout<<ans;    return 0;}

 

【贪心】洛谷P1803 凌乱的yyy