310238: CF1802D. Buying gifts
Description
There are $n$ departments in the mall, each of which has exactly two stores. For convenience, we number the departments with integers from $1$ to $n$. It is known that gifts in the first store of the $i$ department cost $a_i$ rubles, and in the second store of the $i$ department — $b_i$ rubles.
Entering the mall, Sasha will visit each of the $n$ departments of the mall, and in each department, he will enter exactly one store. When Sasha gets into the $i$-th department, he will perform exactly one of two actions:
- Buy a gift for the first friend, spending $a_i$ rubles on it.
- Buy a gift for the second friend, spending $b_i$ rubles on it.
Sasha is going to buy at least one gift for each friend. Moreover, he wants to pick up gifts in such a way that the price difference of the most expensive gifts bought for friends is as small as possible so that no one is offended.
More formally: let $m_1$ be the maximum price of a gift bought to the first friend, and $m_2$ be the maximum price of a gift bought to the second friend. Sasha wants to choose gifts in such a way as to minimize the value of $\lvert m_1 - m_2 \rvert$.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1\,000$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($2 \le n \le 500\,000$) — the number of departments in the mall.
Each of the following $n$ lines of each test case contains two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$) — the prices of gifts in the first and second store of the $i$ department, respectively.
It is guaranteed that the sum of $n$ over all test cases does not exceed $500\,000$.
OutputPrint one integer — the minimum price difference of the most expensive gifts bought to friends.
ExampleInput
2 2 1 2 2 1 5 1 5 2 7 3 3 4 10 2 5Output
0 1Note
In the first test case, Sasha has two possible options: buy a gift for the first friend in the first department, and the second friend — in the second department, or vice versa. In the first case, $m_1 = m_2 = 1$, and in the second case — $m_1 = m_2 = 2$. In both cases, the answer is $0$. In the second test case, you can buy gifts for the first friend in the $2$, $4$ and $5$ departments, and for the second friend — in the $1$ and $3$ departments.So $m_1 = \max(2, 4, 2) = 4$, $m_2 = \max(5, 3) = 5$. The answer is $\lvert 4 - 5 \rvert = 1$.
Input
Output
小萨沙想给两个朋友在3月8日买礼物，为此他去了城里最大的购物中心。购物中心有n个部门，每个部门有两个商店，分别编号为1到n。已知第i部门第一个商店的礼物价格为a_i卢布，第二个商店的价格为b_i卢布。萨沙会进入每个部门的其中一个商店购买礼物，要么为第一个朋友花费a_i卢布，要么为第二个朋友花费b_i卢布。萨沙想为每位朋友至少买一个礼物，并且希望两位朋友收到的最贵礼物价格差尽可能小。形式上，设m_1为给第一个朋友买的礼物中的最高价格，m_2为给第二个朋友买的礼物中的最高价格，萨沙想最小化|m_1 - m_2|的值。
输入数据格式：
输入包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 1,000）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 500,000）——购物中心的部门数。
接下来n行，每行包含两个整数a_i和b_i（0 ≤ a_i, b_i ≤ 10^9）——第i部门两个商店的礼物价格。
所有测试用例的n之和不超过500,000。
输出数据格式：
打印一个整数——给朋友购买的最贵礼物之间的最小价格差。
示例：
输入：
2
2
1 2
2 1
5
1 5
2 7
3 3
4 10
2 5
输出：
0
1
注意：
在第一个测试用例中，萨沙有两种选择：在第一个部门给第一个朋友买礼物，在第二个部门给第二个朋友买，或者反过来。两种情况下，m_1 = m_2，答案为0。在第二个测试用例中，萨沙可以在第2、4、5部门给第一个朋友买礼物，在第1、3部门给第二个朋友买。所以m_1 = max(2, 4, 2) = 4，m_2 = max(5, 3) = 5。答案为|4 - 5| = 1。题目大意： 小萨沙想给两个朋友在3月8日买礼物，为此他去了城里最大的购物中心。购物中心有n个部门，每个部门有两个商店，分别编号为1到n。已知第i部门第一个商店的礼物价格为a_i卢布，第二个商店的价格为b_i卢布。萨沙会进入每个部门的其中一个商店购买礼物，要么为第一个朋友花费a_i卢布，要么为第二个朋友花费b_i卢布。萨沙想为每位朋友至少买一个礼物，并且希望两位朋友收到的最贵礼物价格差尽可能小。形式上，设m_1为给第一个朋友买的礼物中的最高价格，m_2为给第二个朋友买的礼物中的最高价格，萨沙想最小化|m_1 - m_2|的值。 输入数据格式： 输入包含多个测试用例。第一行包含测试用例数t（1 ≤ t ≤ 1,000）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 500,000）——购物中心的部门数。 接下来n行，每行包含两个整数a_i和b_i（0 ≤ a_i, b_i ≤ 10^9）——第i部门两个商店的礼物价格。 所有测试用例的n之和不超过500,000。 输出数据格式： 打印一个整数——给朋友购买的最贵礼物之间的最小价格差。 示例： 输入： 2 2 1 2 2 1 5 1 5 2 7 3 3 4 10 2 5 输出： 0 1 注意： 在第一个测试用例中，萨沙有两种选择：在第一个部门给第一个朋友买礼物，在第二个部门给第二个朋友买，或者反过来。两种情况下，m_1 = m_2，答案为0。在第二个测试用例中，萨沙可以在第2、4、5部门给第一个朋友买礼物，在第1、3部门给第二个朋友买。所以m_1 = max(2, 4, 2) = 4，m_2 = max(5, 3) = 5。答案为|4 - 5| = 1。