1400-高级钟点秘书


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:6 提交数:11 难度:1


题目描述:

所谓钟点秘书,是指年轻白领女性利用工余时间为客户提供秘书服务,并按钟点收取酬金。钟点秘书为客户提供有偿服务的方式一般是:采用电话、电传、上网等遥控式服务,或亲自到客户公司处理部分业务。某跨国公司总裁正分身无术,为一大堆会议时间表焦头烂额,希望高级钟点秘书能做出合理的安排,能在有限的时间内召开更多的会议。每个会议i都有起始时间bi和结束时间ei,且bi<ei,即一个会议进行的时间为半开区间[biei)。如果[biei)与[bjej)均在有限的时间内,且不相交,则称会议i与会议j相容的。也就是说,当biejbjei时,会议i与会议j相容。会议安排问题要求在所给的会议集合中选出最大的相容活动子集,即尽可能在有限的时间内召开更多的会议。


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行,每行有两个正整数bi,ei(0<=bi,ei<24),分别表示第i个活动的开始与结束时间(bi<ei)。

输出描述:

对于每一组输入,输出最多能够安排的会议数量。
每组的输出占一行。

样例输入:

2
10
3 6
1 4
5 7
2 5
5 9
3 8
8 11
6 10
8 12
12 14
5
8 12
9 10
13 16
16 18
9 12

样例输出:

4
3

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!