【Codeforces Round #601 (Div. 2) B】Math Problem 贪心

Your math teacher gave you the following problem:

There are n segments on the x-axis, [l1;r1],[l2;r2],…,[ln;rn]. The segment [l;r] includes the bounds, i.e. it is a set of such x that l≤x≤r. The length of the segment [l;r] is equal to r−l.

Two segments [a;b] and [c;d] have a common point (intersect) if there exists x that a≤x≤b and c≤x≤d. For example, [2;5] and [3;10] have a common point, but [5;6] and [1;4] don’t have.

You should add one segment, which has at least one common point with each of the given segments and as short as possible (i.e. has minimal length). The required segment can degenerate to be a point (i.e a segment with length zero). The added segment may or may not be among the given n segments.

In other words, you need to find a segment [a;b], such that [a;b] and every [li;ri] have a common point for each i, and b−a is minimal.

Input
The first line contains integer number t (1≤t≤100) — the number of test cases in the input. Then t test cases follow.

The first line of each test case contains one integer n (1≤n≤105) — the number of segments. The following n lines contain segment descriptions: the i-th of them contains two integers li,ri (1≤li≤ri≤109).

The sum of all values n over all the test cases in the input doesn’t exceed 105.

Output
For each test case, output one integer — the smallest possible length of the segment which has at least one common point with all given segments.

Example
Input
4
3
4 5
5 9
7 7
5
11 19
4 17
16 16
3 12
14 17
1
1 10
1
1 1
Output
2
4
0
0
Note
In the first test case of the example, we can choose the segment [5;7] as the answer. It is the shortest segment that has at least one common point with all given segments.

题意：给n个区间，要你找出一个长度最小（这里定义为R-L）的区间，能与这n个区间有交集

思路（贪心）：

因为每个区间只要有一个点就能代表一个这个区间，那么我们会想让每个区间尽量在端点取代表。要找到一个区间覆盖以上所有区间，那我这个区间右端点肯定是包含“最后一个区间”的开始位置，和最前面那个区间的“结束位置”，这样就使得右端点尽可能小，左端点尽可能大。那么这个最后一个区间的左端点，自然就是n个区间中最大的L，最前面的区间的结束位置就是n个区间内最小的R，那么求的这两个L，R，结果就是max( L-R,0 )，注意是L-R，因为取得是最右的左端点和最左的右端点，这里可能有包含关系所以和0对比取大。

#include <bits/stdc++.h>
#define maxn 100000
using namespace std;

typedef struct information{
        int l;
        int r;
}L;
L a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    int kase;
    cin>>kase;
    while(kase--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r;
        int L=a[1].l, R=a[1].r;
        for(int i=2;i<=n;i++)
        L = max(a[i].l,L) , R = min(R, a[i].r);
        if(n!=1)
        cout<<max(L-R,0)<<endl;
        else cout<<0<<endl;
    }
    return 0;
}