Codeforces #613 Div2 E. Delete a Segment

ちょっと悩む問題。
http://codeforces.com/contest/1285/problem/E

問題

1次元の数直線上でN個の区間が与えられる。
共通部分を持つ区間を1つにマージすること考える。

元のN個から1個取り除いた時、マージ後の区間数の最大値を求めよ。

解法

まず各区間の登場順をソートし、マージ後の区間の先頭または2番目になりうるかを求めておこう。
また、2番目である際は1番目の番号を覚えておく。

ある区間を削除すると、その区間が先頭の場合は区間数が1個減るが、代わりにその区間を1番目にしている2番目の区間の数だけ区間数が増加する。
これをもとに、削除する区間を総当たりしよう。

int T;
int N;
ll L[202020],R[202020];
vector<int> ev[402020];
int always[201010],add[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<ll> V;
		V.push_back(-(1LL<<60));
		FOR(i,N) {
			cin>>L[i]>>R[i];
			L[i]*=10000000;
			R[i]*=10000000;
			R[i]+=1000000;
			V.push_back(L[i]);
			V.push_back(R[i]);
		}
		sort(ALL(V));
		
		FOR(i,N) {
			always[i]=add[i]=0;
			L[i]=lower_bound(ALL(V),L[i])-V.begin();
			R[i]=lower_bound(ALL(V),R[i])-V.begin();
			ev[L[i]].push_back(i);
			ev[R[i]].push_back(i);
		}
		set<int> S;
		int al=0;
		FOR(i,V.size()) {
			sort(ALL(ev[i]));
			FORR(e,ev[i]) {
				if(i==L[e]) {
					if(S.empty()) {
						always[e]++;
						al++;
					}
					else if(S.size()==1) {
						add[*S.begin()]++;
					}
					S.insert(e);
				}
				else {
					S.erase(e);
				}
			
			}
			ev[i].clear();
		}
		int ma=0;
		FOR(i,N) {
			ma=max(ma,al-always[i]+add[i]);
		}
		cout<<ma<<endl;
	}
}

まとめ

こういうの時間制限がある中で解くと混乱しそう。