C语言贪心活动选择问题

刺骨的言语ヽ痛彻心扉 2022-06-01 08:05 124阅读 0赞

### 活动选择问题 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### 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 ####

#include <stdio.h>
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            int s1[200];
            int s2[200];
            int i, j, t;
            for(i = 0; i < n; i++)
            {
                scanf("%d %d", &s1[i], &s2[i]);
            }
            for(i = 0; i < n - 1; i++)
            {
                for(j = 0; j < n - i - 1; j++)
                {
                    if(s2[j] > s2[j + 1])
                    {
                        t = s2[j];
                        s2[j] = s2[j + 1];
                        s2[j + 1] = t;
                        t = s1[j];
                        s1[j] = s1[j + 1];
                        s1[j + 1] = t;
                    }
                    else if(s2[j] == s2[j + 1])
                    {
                        if(s1[j] > s1[j + 1])
                        {
                            t = s2[j];
                            s2[j] = s2[j + 1];
                            s2[j + 1] = t;
                            t = s1[j];
                            s1[j] = s1[j + 1];
                            s1[j + 1] = t;
                        }
                    }
                }
            }
            i = 0;
            int count = 0;
            int end = 0;
            while(i < n)
            {
                if(s1[i] >= end)
                {
                    count++;
                    end = s2[i];
                }
                i++;
            }
            printf("%d\n", count);
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2382/pid/2073.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2382/pid/2073.html