AT_tenka1_2012_7 席が足りない

急速成长中的 K 公司，由于招聘速度过快，导致座位数量不足。 虽然下一个办公室的搬迁地点已经确定，但在此之前，必须合理分配有限的座位。 幸运的是，员工的作息时间各不相同，因此如果某人在离开公司后，另一人再来上班，他们可以共用一个座位。 但是，要求员工在上班到下班期间不能更换座位。 此外，公司希望同一个项目的成员能够坐在一起。 即，项目的所有成员都要坐在分配给该项目的座位上，且其他员工不能占用这些座位。 现在给出某个项目中每位成员的上班和下班时间， 请你计算该项目至少需要分配多少个座位。 输入通过标准输入给出，格式如下： $N$ $Ts_1$ $Te_1$ $Ts_2$ $Te_2$ $\vdots$ $Ts_N$ $Te_N$ - 输入共 $N+1$ 行。 - 第 $1$ 行为员工人数 $N$，$1 \leq N \leq 15$。 - 第 $2$ 行到第 $N+1$ 行，第 $i$ 行包含第 $i$ 位员工的上班时间 $Ts_i$（$00:00 \leq Ts_i \leq 23:59$）和下班时间 $Te_i$（$Ts_i < 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$），则可获得 $30$ 分的部分分。 如果你能解决上述两种情况的所有输入，则可获得 $50$ 分的部分分。 请输出项目至少需要分配的座位数，输出一行。 注意，行末需换行。 ``` 3 10:00 12:00 12:00 14:00 14:00 18:00 ``` ``` 1 ``` - 如果上班时间和下班时间相同，可以共用座位。 ``` 3 00:00 09:00 08:00 17:00 16:00 25:00 ``` - $25:00$ 表示次日 $01:00$。 - 在这种情况下，这 $3$ 个人无法共用座位。 ``` 3 ``` ``` 4 00:00 07:00 06:00 13:00 12:00 19:00 18:00 25:00 ``` ``` 2 ```

第 $1$ 行包含一个整数 $N$，表示员工人数。 接下来的 $N$ 行，每行包含两个字符串，分别表示第 $i$ 位员工的上班时间 $Ts_i$ 和下班时间 $Te_i$，以空格分隔。

输出一个整数，表示该项目至少需要分配的座位数。输出后需换行。

- 如果上班时间和下班时间相同，可以共用座位。 - $Te_i \geq 24:00$ 表示次日。 - 从上班到下班的时间不会超过 $24$ 小时。 由 ChatGPT 4.1 翻译