题目解析

问题分析

这是一个在一维数轴上寻找最近空闲点的问题。数轴上有 $n$ 个点（建筑），其中某些区间被占用，学校位于点 $s$（已被占用），需要在未被占用的点中找到距离 $s$ 最近的点。

关键观察

1. 数据规模：$n$ 可以达到 $10^{12}$，不能遍历所有点
2. 区间特性：占用区间互不相交且已排序
3. 候选位置：最近空闲点只可能出现在：
   • 每个占用区间的左边界前一个位置（$l_i - 1$）
   • 每个占用区间的右边界后一个位置（$r_i + 1$）

算法思路

核心思想：检查关键候选点

由于占用区间互不相交，所有空闲建筑必然出现在：

• 第一个区间之前的区域：$[1, l_1 - 1]$
• 相邻区间之间的区域：$[r_i + 1, l_{i+1} - 1]$
• 最后一个区间之后的区域：$[r_m + 1, n]$

但不需要检查所有这些区间内的所有点，因为：

• 在每个空闲区间内，距离学校最近的点必然是区间的端点
• 因此只需要检查每个空闲区间的两个端点

算法步骤

1. 排序区间：确保区间按左端点升序排列
2. 检查关键候选点：
   • 每个占用区间左边界前一个位置（$l_i - 1$）
   • 每个占用区间右边界后一个位置（$r_i + 1$）
3. 验证候选点有效性：确保候选点确实在空闲区间内
4. 选择最优解：在所有有效候选点中选择距离最小、编号最小的

验证候选点有效性

对于候选点 $l_i - 1$：

• 必须满足 $l_i - 1 > r_{i-1}$（即在前一个区间之后）
• 特别地，对于第一个区间：$l_1 - 1 \geq 1$

对于候选点 $r_i + 1$：

• 必须满足 $r_i + 1 < l_{i+1}$（即在后一个区间之前）
• 特别地，对于最后一个区间：$r_m + 1 \leq n$

复杂度分析

• 时间复杂度：$O(m \log m)$，主要来自区间排序
• 空间复杂度：$O(m)$，存储区间信息
• 高效性：将问题规模从 $10^{12}$ 降到 $1000$ 级别

算法正确性

该算法正确的关键在于：

1. 完备性：所有可能的最近空闲点都被考虑
2. 最优性：在多个候选点中选择距离最小、编号最小的
3. 边界处理：正确处理第一个区间之前和最后一个区间之后的情况

样例验证

样例1：

• 区间：$[1,2]$, $[5,9]$，学校在 $7$
• 候选点：$0$（无效）, $3$, $4$, $10$
• $3$ 距离 $|3-7|=4$，$4$ 距离 $3$，$10$ 距离 $3$
• 选择编号最小的 $4$

样例2：

• 区间：$[1,1]$, $[4,5]$, $[6,9]$, $[10,13]$，学校在 $9$
• 候选点：$2$, $3$, $6$（无效，被占用）, $14$
• $2$ 距离 $7$，$3$ 距离 $6$，$14$ 距离 $5$
• 选择 $14$

算法优势

1. 处理大规模数据：不依赖 $n$ 的大小
2. 简单高效：只需要排序和线性扫描
3. 逻辑清晰：易于理解和实现
4. 竞赛友好：适合编程竞赛的时间限制

这种关键点枚举的策略在处理大规模区间问题时非常有效。