贪心算法——活动选择问题

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

题目链接如下:

活动选择问题

最开始先想到让最早开始的活动先进行,但是如果最早开始的活动最晚结束就不满足题目要求,所以为了防止这种情况出现,我们可以采取最早结束的活动最早开始。当然,如果两个活动结束的时间都一样,存在在哪一个活动最早开始问题,但是这个问题可以不用去考虑,因为我们是以最早结束的活动为选择依据的。

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1500;
struct node
{
    int beginTime;
    int endTime;
    node()
    {
        beginTime=0;
        endTime=0;
    }
}a[maxn];

bool cmp(node a,node b)
{
    if(a.endTime!=b.endTime)    /*如果两个活动的结束时间不相等*/
        return a.endTime<b.endTime;
    if(a.endTime==b.endTime)
        return a.beginTime<b.beginTime;
}

int main()
{
    int n,i;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>a[i].beginTime>>a[i].endTime;
    }
    sort(a+1,a+1+n,cmp);
    int cnt=0;
    int tmp=-1;/*用于进行贪心选择的变量*/
    for(i=1; i<=n; i++)/*进行活动选择 */
    {
        if(a[i].beginTime >= tmp)
        {
            tmp=a[i].endTime;
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

 

 

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《贪心算法——活动选择问题》 发布于2019-06-06

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录