問題文
急速成长中的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 永远不会超过一个小时。
部分点
此外,所有员工 输入 23:59 离开公司( 1 \leq i \leq N 反对 Te_i \leq 23:59 ) 是正确的,那么100 部分积分换满分 30 点。 如果您正确回答了所有满足
上記 2 如果满足其中一个条件的所有输入都得到正确回答,100 部分积分换满分 50 点。 如果您正确回答了所有满足
出力
请注意,行尾需要换行。 定义
入力例 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