P13169 [GCJ 2017 #1C] Parenting Partnering

Cameron 和 Jamie 是多年的生活伴侣，最近刚刚成为了父母！照顾婴儿虽然令人兴奋，但也充满挑战。由于两位父母都具有科学思维，他们决定以科学的方法来照顾孩子。 Cameron 和 Jamie 正在制定每日作息时间表，需要决定在每天的每个时刻由谁主要负责照看婴儿。他们一直以来都是平等的伴侣，现在也不想改变这一点，因此他们决定每天各自负责照看婴儿恰好 12 小时（720 分钟）。 Cameron 和 Jamie 各自还有一些必须或想要独自完成的活动。Cameron 有 $A_C$ 个这样的活动，Jamie 有 $A_J$ 个。这些活动每天都在相同的时间进行。Cameron 的活动与 Jamie 的活动不会重叠，因此至少有一位父母始终可以照看婴儿。 Cameron 和 Jamie 想要制定一个每日照看婴儿的时间表，使得： - 安排的照看时间不能与已安排的活动冲突。也就是说，在 Cameron 有活动时，Jamie 必须负责照看婴儿，反之亦然。 - Cameron 和 Jamie 每人分配的照看时间必须恰好为 720 分钟。 - 交接次数——即负责照看婴儿的人从一方变为另一方的次数——要尽可能少。 例如，假设 Jamie 和 Cameron 各有一项活动：Jamie 有一项早上 9 点到 10 点的活动，Cameron 有一项下午 2 点到 3 点的活动。一种可能但非最优的安排是，Jamie 从午夜到早上 6 点以及中午到下午 6 点照看婴儿，Cameron 从早上 6 点到中午以及下午 6 点到午夜照看婴儿。这样满足前两个条件，总共需要 4 次交接，分别发生在午夜、早上 6 点、中午和下午 6 点。如果交接发生在午夜，只计作一次，不计作零次或两次。 更优的方案是 Cameron 从午夜到中午照看婴儿，Jamie 从中午到午夜照看婴儿。这个安排同样满足前两个条件，但只需要 2 次交接，这是最少可能的次数。 给定 Cameron 和 Jamie 的活动列表，以及上述限制，问每日时间表中最少需要多少次交接？

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试用例。每组测试用例的第一行为两个整数 $A_C$ 和 $A_J$，分别表示 Cameron 和 Jamie 的活动数。接下来的 $A_C + A_J$ 行，每行包含两个整数。前 $A_C$ 行，每行包含两个整数 $C_i$ 和 $D_i$，表示 Cameron 的第 $i$ 个活动从午夜起第 $C_i$ 分钟开始，到第 $D_i$ 分钟结束（持续 $D_i - C_i$ 分钟）。接下来的 $A_J$ 行，每行包含两个整数 $J_i$ 和 $K_i$，表示 Jamie 的一项活动的开始和结束时间（同样以午夜起的分钟数计）。没有活动跨越两天，且任意两项活动不会重叠（但可能一个活动结束时另一个活动正好开始，此时可以发生交接）。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为最少的交接次数。

**样例解释** 注意，样例 #4 和 #5 不会出现在 Small 数据集。 样例 #1 即题目描述中的例子。 在样例 #2 中，Jamie 必须覆盖 Cameron 所有活动的时间，然后 Cameron 覆盖剩余的时间。这个安排需要 4 次交接。 在样例 #3 中，午夜时有一次从 Cameron 到 Jamie 的交接。无论父母如何分配剩余的 $1438$ 分钟非活动时间，至少还需要一次从 Jamie 到 Cameron 的交接，没有理由增加更多交接。 在样例 #4 中，注意同一方或不同方的活动可能连续出现。由于 Cameron 在午夜前后都有活动，因此午夜没有交接。但在 Jamie 的活动之间需要为 Cameron 安排一段时间，总共需要 4 次交接。最优做法是在第 2 分钟到第 1438 分钟之间为 Cameron 安排一段长度为 718 分钟的区间，具体位置不影响交接次数，因此存在多种最优方案。 在样例 #5 中，一种最优方案是将 Cameron 分配到区间（以分钟计）$100-200$、$500-620$ 和 $900-1400$。 **数据范围** - $1 \leq T \leq 100$。 - 对所有 $i$，$0 \leq C_i < D_i \leq 24 \times 60$。 - 对所有 $i$，$0 \leq J_i < K_i \leq 24 \times 60$。 - 所有 $\{[C_i, D_i)\}$ 与 $\{[J_i, K_i)\}$ 区间两两不重叠（区间左闭右开，确保两个完全连续的区间之间没有重叠，但也没有间隙）。 - $\sum (D_i - C_i)$ 对所有 $i$ 不超过 720。 - $\sum (K_i - J_i)$ 对所有 $i$ 不超过 720。 **Small 数据集（测试集 1 - 可见）** - $0 \leq A_C \leq 2$。 - $0 \leq A_J \leq 2$。 - $1 \leq A_C + A_J \leq 2$。 **Large 数据集（测试集 2 - 隐藏）** - $0 \leq A_C \leq 100$。 - $0 \leq A_J \leq 100$。 - $1 \leq A_C + A_J \leq 200$。 由 ChatGPT 4.1 翻译