设为首页 加入收藏

TOP

A.Activity planning
2018-11-19 22:13:08 】 浏览:30
Tags:A.Activity planning

题目描述
There is a collection of n activities E={1,2,..,n}, each of which requires the same resource, such as
a lecture venue, etc., and only one activity at a time Use this resource. Each activity i has a start
time of si and an end time of fi and si<fi. If the activity i is selected, it occupies resources within
the time interval [si,fi). If the interval [si,fi) does not intersect the interval [sj,fj), then the activity i is
said to be compatible with the activity j. That is, when fi<=sj or fj<=si, the activity i is compatible
with the activity j . Choose the largest collection of activities that are compatible with each other.
输入格式
The first line is an integer n;
The next n line, two integers per line, si and fi.
输出格式
Excluding mutual and compatible maximum active number.
样例输入1
4
1 3
4 6
2 5
1 7
样例输出1
2

数据范围与提示
1<=n<=1000

 

这道题解法与杭电今年暑假不AC解法相同,采用均摊法

代码实例

#include<stdio.h>

struct huodong
{
    int begin;
    int end;
} J[1002];

int main()
{
    int n,i,j,sum,temp;
    sum = 1;
    scanf("%d",&n);
    for(i=0; i<n; i++)
        scanf("%d %d",&J[i].begin,&J[i].end);
    for(i=0; i<n-1; i++)
    {
        for(j=0; j<n-i-1; j++)
        {
            if(J[j].end>J[j+1].end)
            {
                temp = J[j].end;
                J[j].end = J[j+1].end;
                J[j+1].end = temp;

                temp = J[j].begin;
                J[j].begin = J[j+1].begin;
                J[j+1].begin = temp;
            }
        }
    }
    temp = J[0].end;
    for(i=1; i<n; i++)
    {
        if(J[i].begin>=temp)
        {
            sum++;
            temp = J[i].end;
        }
    }
    printf("%d\n",sum);
    return 0;
}

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇猴子选大王问题 下一篇c语言实现求解这样的6位数:SQRT(6..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }