C1016 - 安排最多的会议

题目描述

小明是一家公司的秘书,老板的会议都是由他来安排的,小明知道一天中的所有的会议的起始时间和结束时间,老板要求在某个时间段里给他安排尽可能多的会议,现在由你来帮小明写个程序来实现这个要求。

每一个会议有一个起始时间b和一个结束时间e,b < e,会议进行的时间是一个半开区间[b, e),包含开头时刻,不包含结束时刻,举个例子来说:

会议1:开始时间:2,结束时间:5,会议时间是[2, 5),是连续的时间段

会议2:开始时间:5,结束时间:10,会议时间是[5, 10),是连续的时间段

那么这两个会议是不冲突的,是相容的,可以同时安排这两个会议,但如果有另一个会议:

会议3:开始时间:3,结束时间:6,则会议1与会议3的会议时间是相交的,是有冲突的,不能同时安排这两个会议

现在给出所有的会议时间,和特定的时间段,请帮小明计算出可以帮老板在该特定的时间段里能安排的最多的会议数量是多少?

所有会议时间、给定的特定的时间段都是一段连续的时间段

输入格式

第1行,一个正整数n,代表一共有多少场会议

接下来n行,代表n场会议的信息,每一行有两个正整数,第1个表示会议的开始时间,第2个表示会议的结束时间,两个正整数用空格分隔

最行1行,两个正整数,代表一个可以安排会议的特定时间段,有两个正整数,代表特定时间段的开始时间和特定时间段的结束时间

输出格式

1行,1个正整数,代表在特定的时间段里最多可以安排的会议数量

输入输出样例

输入样例 输出样例
10
8 10
9 11
10 15
11 14
13 16
14 17
15 17
17 18
18 20
16 19
8 20
5
6
10 12
11 14
14 15
14 16
17 20
18 19
13 19
2

样例说明

以第1组样例数据做说明:

输入样例说明

第1行:10,代表接下来会有10场会议的信息

接下来的10行:每行代表一场会议的信息,两个整数,分别代表:会议的开始时间和会议的结束时间,比如8 10,代表会议的时间是[8, 10)

最后1行:代表可以安排会议的特定的时间段8 - 20,也就是要根据所有的会议信息计算出在[8, 20]这个时间段里最多可以安排的会议的数量是多少

输出样例说明

5,代表在[8, 20]这个时间段里最多可以安排的会议数量是5

数据范围与提示

100%的数据:$1 \le n \le 20$,1 ≤ 开始时间 < 结束时间 ≤ 23

测试点数目

共10个测试点,每个测试点10分

时间与内存限制

每个测试点时间:1000ms(1.0s),内存:256MiB

输入输出模式

本OJ支持两种输入输出模式

1. 标准输入输出模式:
直接从标准输入和标准输出读写数据,不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式(国内信奥赛输入输出模式):
从文件中读写数据,需要使用freopen进行输入输出重定向
本题输入文件名为:C1016.in,输出文件名为:C1016.out