HDOJ 2037 今年暑假不AC

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2037

思路：先把时间表按结束时间从小到大排列，然后可以推断出，结束时间te最小的节目一定在最长序列里。然后以结束时间尽量小的顺序接着找开始时间比上一个已确定的节目结束时间大且尽量晓得节目。

表达有点困难，大家分析下代码，应该不难。

// Author: Tanky Woo
// HDOJ 2037
#include 
#include 
using namespace std;

typedef struct TIME
{
    int ts;
    int te;
}TIME;

TIME time_table[101];
// www.wutianqi.com
int cmp(TIME a, TIME b)
{
    return (a.te < b.te);
}

int n;
int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d", &n;) && n)
    {
        for(int i = 0; i < n; ++i)
            scanf("%d %d", &time;_table[i].ts, &time;_table[i].te);
        sort(time_table, time_table+n, cmp);   //按te由小到大排列
        //for(int i = 0; i < n; ++i)
            //printf("%d %d\n", time_table[i].ts, time_table[i].te);
        // 目的:是te尽量小的同时,再使ts也尽量小
        int cnt = 0, sum = 1;  //最小的te的那个节目是一定要包括进去的
        for(int i = 1; i < n; ++i)
        {
            if(time_table[i].ts >= time_table[cnt].te)
            {
                cnt = i;
                sum++;
            }
        }
        printf("%d\n", sum);

    }
    return 0;
}