活动安排问题

2013年12月7日3,2060

来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1133

题目描述

设有n(n<=100000)个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

输入

每行2个整数（100000以内），用空格间隔。表示每个活动的起始和结束时间。最后一行是2个0，表示所有输入的结束。

输出

一个整数，表示最多能安排几个活动。

样例输入

1 2 1 4 1 3 2 3 0 0

样例输出

代码

#include<iostream>
#include<algorithm>
using namespace std;
struct data{
    int b,d;
}a[100001];
int gz(const data &a,const data &b)
{
    if(a.d<b.d)return 1;
    else return 0;
}
int main()
{
    int i=0;
    while(cin>>a[i].b>>a[i].d)
    {
        if(a[i].b==0&&a[i].d==0){i--;break;}
        i++;
	}
    sort(a,a+i,gz);
    int end=0,ans=0;
    for(int j=0;j<=i;j++)
       if(a[j].b>=end)
       {
			end=a[j].d;
			ans++;
	}
    cout<<ans;
    return 0;
}

#include<iostream>

#include<algorithm>

using namespace std;

struct data{

int b,d;

}a[100001];

int gz(const data &a,const data &b)

{

if(a.d<b.d)return 1;

else return 0;

}

int main()

{

int i=0;

while(cin>>a[i].b>>a[i].d)

{

if(a[i].b==0&&a[i].d==0){i--;break;}

i++;

}

sort(a,a+i,gz);

int end=0,ans=0;

for(int j=0;j<=i;j++)

if(a[j].b>=end)

{

end=a[j].d;

ans++;

}

cout<<ans;

return 0;

}

比较简单的贪心，按照结束时间排序，一个个判断能不能取，end记录最后取的那个活动的结束时间。

应该比较好理解

« NOIP1999拦截导弹「RQNOJ255」排队接水 »

hzwer.com _ Home | http://hzwer.com

活动安排问题

题目描述

输入

输出

样例输入

样例输出

代码

分类目录

热门文章

Myfriends

近期评论