codeforces edu #29 E. Turn Off The TV (思维，乱搞)
题意：有若干线段，给出起点和终点，问是否有一个线段是冗余的。冗余的意思是说，对于该线段所覆盖的所有整数点，没有该线段，也能被其他一个或者多个线段覆盖到。如果有，输出任意一个冗余线段即可。
思路：画画图？ 显然可以按照第一关键字左端点升序，第二关键字右端点降序（降序是为了处理 n=2,[1,2],[1,3] 这样的case容易一些），先考虑2种最简单的情况。
第一种是a[i+1]完全被a[i]包裹在里面，准确得说不一定是a[i]，而是之前所有线段的最大右端点的那条线段，此时a[i+1]就是冗余的线段。
第二种是a[i+1]的左端点在之前所有线段的最大右端点右边，此时没有冗余，继续进行。
接下来考虑比较复杂的相交情况，我们画图发现，当前线段是否冗余，只与a[i-1]和a[i+1]有关。
如果第i条线段的左端点，不超过第i-2条线段的右端点的右边一个位置，此时第i-1条线段就是冗余的。
wa了2次。。原因是没认真看题，l,r的范围的最小值是从0开始而不是1。所以总体来说是道水题（调教场的题这么水了么。。。
/* ***********************************************
Author :111qqz
Created Time :2017年09月25日 星期一 02时57分03秒
File Name :E.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E5+7;
7struct Node
8{
9 int l,r;
10 int id;
11}a[N];
12int n;
13int ans;
14vector<int>ret;
15bool cmp( Node x, Node y)
16{
17 if (x.l==y.l) return x.r>y.r;
18 return x.l<y.l;
19}
20int main()
21{
22 #ifndef ONLINE_JUDGE
23 freopen("./in.txt","r",stdin);
24 #endif
25 cin>>n;
26 for ( int i = 1 ; i <= n ; i++)
27 {
28 scanf("%d %d",&a[i].l,&a[i].r);
29 a[i].id = i;
30 }
31 sort(a+1,a+n+1,cmp);
32 ans = 0 ;
33 int mxR=-1;
34 int lsR=-1;
35 for ( int i = 1 ; i <= n ; i++)
36 {
37 //puts("miao");
38 if (i>=3) lsR=a[i-2].r;
39 if (a[i].r<=mxR)
40 {
41 ans++;
42 ret.push_back(a[i].id);
43 }
44 else if (a[i].l>=mxR+1) //先考虑最easy的2个情况.
45 {
46 mxR=max(mxR,a[i].r);
47 }else if (lsR!=-1&&a[i].l<=lsR+1&&a[i].r)
48 {
49 ans++;
50 ret.push_back(a[i-1].id);
51 }
1 mxR = max(mxR,a[i].r);
2 }
3 if (ans==0) ans=-1;
4 else ans = ret[0];
5 printf("%d\n",ans);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}