解题思路
先把题意转化一下。
你需要选一个整数位置 x，要求它不能落在任何一个人的禁区 [li,ri] 中，也就是 x 不能被这些区间的并集覆盖。同时要让你走的距离 ∣x−p∣ 最小。
所以问题本质上就是：
给定若干个区间，求离 p 最近的、不在这些区间并集内 的整数点。
P4806.第2题-最短就餐距离
题目内容
在一条无限长的美食街上，每个整数坐标处都有一家餐厅。你当前位于位置 p。
现在共有n个人（包括你自己），第i 个人不愿意去区间[li,ri]内的任何餐厅。你需要选择一个餐厅位置x∈Z，使得对所有人都 “可接受”（即x∈/[li,ri]对所有 i成立），并且使你走的距离∣x−p∣ 最小。请输出这个最小距离。
输入描述
每个测试文件均包含多组测试数据：第一行输入一个整数T(1≤T≤2×105)，代表数据组数。每组测试数据描述如下：
- 每组数据第一行输入两个整数 n,p(1≤n≤2×105，−106≤p≤106)；
- 接下来 n 行，每行输入两个整数 li,ri(−106≤li≤ri≤106)。
保证所有测试中 n的总和不超过 5×105。
输出描述
输出T行，每行输出一个整数，为最小距离。
样例1
输入
3
2 5
1 3
7 8
1 10
10 20
3 0
-2 1
2 4
6 9
输出
0
1
3
说明
- 样例1：禁用区间为[1,3]∪[7,8]，位置p=5可直接就餐，距离为0。
- 样例 2：最近不在禁区内的餐厅位置是9，距离为∣9−10∣=1。
