51Nod 1091 线段的重叠（贪心）

X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，[10 20]和[12 25]的重叠部分为[12 20]。

给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。

Input

第1行：线段的数量N(2 <= N <= 50000)。
第2 - N + 1行：每行2个数，线段的起点和终点。(0 <= s , e <= 10^9)

Output

输出最长重复区间的长度。

Input示例

Output示例

4

思路：利用sort之后的数组，进行O(N)扫

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <cstdlib>
 7 #include <iomanip>
 8 #include <cmath>
 9 #include <ctime>
10 #include <map>
11 #include <set>
12 using namespace std;
13 #define lowbit(x) (x&(-x))
14 #define max(x,y) (x>y?x:y)
15 #define min(x,y) (x<y?x:y)
16 #define MAX 100000000000000000
17 #define MOD 1000000007
18 #define pi acos(-1.0)
19 #define ei exp(1)
20 #define PI 3.141592653589793238462
21 #define INF 0x3f3f3f3f3f
22 #define mem(a) (memset(a,0,sizeof(a)))
23 typedef long long ll;
24 const int N=50005;
25 const int mod=1e9+7;
26 struct node
27 {
28     int x,y;
29 }p[50001];
30 int cmp(node a,node b)
31 {
32     if(a.x!=b.x) return a.x<b.x;
33     else return a.y<b.y;
34 }
35 int main()
36 {
37     int n,i,j,maxn=0;
38     scanf("%d",&n);
39     for(i=0;i<n;i++)
40         scanf("%d%d",&p[i].x,&p[i].y);
41     sort(p,p+n,cmp);
42     int m=p[0].y;
43     for(i=1;i<n;i++){
44         if(p[i].y>=m)  {
45             maxn=max(maxn,m-p[i].x);
46             m=p[i].y;
47         }
48         else maxn=max(maxn,p[i].y-p[i].x);
49     }
50     printf("%d
",maxn);
51     return 0;
52 }

51Nod 1091 线段的重叠 （贪心）

51Nod 1091 线段的重叠（贪心）