SDUT 贪心活动选择问题

Problem Description

sdut 大学生艺术中心每天都有n个活动申请举办，但是为了举办更多的活动，必须要放弃一些活动，求出每天最多能举办多少活动。
Input

输入包括多组输入，每组输入第一行为申请的活动数n(n<100)，从第2行到n+1行，每行两个数，是每个活动的开始时间b，结束时间e；
Output

输出每天最多能举办的活动数。
Example Input

12
15 20
15 19
8 18
10 15
4 14
6 12
5 10
2 9
3 8
0 7
3 4
1 3
Example Output

5
Hint

Author

比上一个活动选择简单不少，大概是相同的，一个是输出活动的序号，这个是输出一共多少活动。

代码


#include <stdio.h>
struct node
{
    int begin,end;
}act[101],tem;

void qsort(int l,int r)
{
    int i=l,j=r;
    tem = act[i];
    if(i>=j) return;
    while(i<j)
    {
        while(i<j&&act[j].end>=tem.end) j--;
        act[i] =act[j];
        while(i<j&&act[i].end<=tem.end) i++;
        act[j] = act[i];
    }
    act[i] = tem;
    qsort(l,i-1);
    qsort(i+1,r);
}

int main()
{
    int n,i,sum,timestart;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
        {
            scanf("%d %d",&act[i].begin,&act[i].end);
        }
        qsort(0,n-1);
        sum = 0;
        timestart = 0;
        for(i=0;i<n;i++)
        {
             if(act[i].begin>=timestart)
             {
                timestart = act[i].end;
                sum++;
             }
        }
        printf("%d\n",sum);
    }
    return 0;
}

SDUT 贪心 活动选择问题

推荐阅读

SDUT 贪心活动选择问题