P16725 [GKS 2019 #A] Contention

你正在销售电影院前排座位的门票。前排有 $N$ 个座位，从左到右编号为 $1$ 到 $N$。你上周不在办公室，回来时发现积压了 $Q$ 个座位预订！第 $i$ 个预订请求从 $L_i$ 到 $R_i$（包含两端）的所有座位。你现在需要将这些预订逐一输入系统，这是一项枯燥的工作。 由于某些预订可能重叠，系统可能无法完全满足每个预订。当你将一个预订输入系统时，系统会分配该预订请求的、且尚未被更早输入的预订所分配的所有座位。 请问，最大的整数 $k$ 是多少，使得存在一种输入预订的顺序，让每个预订都被分配到至少 $k$ 个座位？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $Q$，分别表示座位数量和预订数量。随后有 $Q$ 行，其中第 $i$ 行包含两个整数 $L_i$ 和 $R_i$，表示第 $i$ 个预订希望预订从 $L_i$ 到 $R_i$（包含两端）的所有座位。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述最大的 $k$ 值。

在样例 #1 中，有 $N = 5$ 个座位和 $Q = 3$ 个预订。一种可能的顺序是： - 先输入第二个预订，系统会分配 $2$ 个座位（$3$ 和 $4$）。 - 再输入第一个预订，系统会分配 $2$ 个座位（$1$ 和 $2$）。 - 最后输入第三个预订，系统会分配 $1$ 个座位（仅剩座位 $5$，因为 $1$、$2$、$3$、$4$ 已被预订）。 每个预订都被分配到至少 $1$ 个座位，且不存在一种顺序能让每个预订分配到至少 $2$ 个座位，因此答案为 $1$。 在样例 #2 中，有 $N = 30$ 个座位和 $Q = 3$ 个预订。无论以何种顺序分配座位，至少有一个预订将分不到任何座位，所以答案为 $0$。注意，可能存在不属于任何预订的座位！ 在样例 #3 中，有 $N = 10$ 个座位和 $Q = 4$ 个预订。一种可能的顺序是： - 先输入第二个预订，系统会分配 $2$ 个座位（$4$ 和 $5$）。 - 再输入第三个预订，系统会分配 $2$ 个座位（$3$ 和 $6$，因为 $4$ 和 $5$ 已被预订）。注意，分配到的座位不一定相邻。 - 接着输入第四个预订，系统会分配 $2$ 个座位（$2$ 和 $7$）。 - 最后输入第一个预订，系统会分配 $2$ 个座位（$1$ 和 $8$）。 每个预订都被分配到至少 $2$ 个座位，且不存在一种顺序能让每个预订分配到至少 $3$ 个座位，因此答案为 $2$。 **注意**：对于本题的大数据集，我们不建议使用解释型/较慢的语言。 ### 限制条件 $T = 100$。 $1 \le N \le 10^6$。 $1 \le L_i \le R_i \le N$。 **测试集 1（可见）** $1 \le Q \le 300$。 **测试集 2（隐藏）** $1 \le Q \le 30000$。 在至少 $85$ 个测试用例中，$Q \le 3000$。 翻译由 DeepSeek V4 Pro 完成