← 返回题目列表

AtCoder · tenka1_2012_7

C. 座位不足

中文机器翻译题面 查看原题

問題文

急速成长中的K公司,由于采用过快,座位不够用了。
下一个办公地点已经决定,但在那之前我们必须利用有限的座位。

幸运的是,我们的员工有不同的生活方式,所以如果一个人离开办公室,另一个人来上班,我们决定共用座位。
但是,我希望避免从上班到离开期间更换座位。

我也喜欢按项目坐在一起。
所有项目员工都坐在分配给该项目的座位上。
我想阻止其他员工坐在分配给该项目的座位上。

由于给出了某个项目每个员工的到达和离开时间,
找出应分配给该项目的最小席位数。


入力

输入是按以下格式从标准输入给出的。
N
Ts_1 Te_1
Ts_2 Te_2
:
:
Ts_N Te_N
  • 输入是 N+1 。
  • 1 行代表员工人数。 N ( 1 \leq N \leq 15 )。
  • 2 从线 N 行有 i ( 1 \leq i \leq N )第名员工到达时间 Ts_i ( 00:00 \leq Ts_i \leq 23:59 ) 和离开时间 Te_i ( Ts_i \lt Te_i \leq 35:59 ) 作为空格分隔符给出。
  • Te_i \geq 24:00 表示第二天。
  • 上班到下班的时间 24 永远不会超过一个小时。

部分点

项目投入很少( 1 \leq N \leq 8 ) 是正确的,那么100 部分积分换满分 20 点。 如果您正确回答了所有满足
此外,所有员工 输入 23:59 离开公司( 1 \leq i \leq N 反对 Te_i \leq 23:59 ) 是正确的,那么100 部分积分换满分 30 点。 如果您正确回答了所有满足
上記 2 如果满足其中一个条件的所有输入都得到正确回答,100 部分积分换满分 50 点。 如果您正确回答了所有满足

出力

显示必须在标准输出上分配给项目的最小席位数。 1 行。
请注意,行尾需要换行。 定义

入力例 1

3
10:00 12:00
12:00 14:00
14:00 18:00

出力例 1

1
  • 如果您的抵达和出发时间相同,则可以共用座位。

入力例 2

3
00:00 09:00
08:00 17:00
16:00 25:00
  • 25:00 是第二天 01:00 的意思。
  • 在这种情况下,这个 3 人们不能共享座位。

出力例 2

3

入力例 3

4
00:00 07:00
06:00 13:00
12:00 19:00
18:00 25:00

出力例 3

2