Codeforces Round #613 (Div. 2): E. Delete a Segment

https://codeforces.com/contest/1285/problem/E

問題
区間を1つ選んで削除した後に残った重なる区間をunionする。
unionした後に残る区間の数を最大化せよ。

解法
全区間をunionした後に残る区間の数は、区間を始点ソートして昇順ループまたは降順ループを回して求めることができる。
それらをいい感じにハイブリッドすると通った。

int n;
pair<int, int> seg[200000];
int last[200000];
int cnt[200000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	rep(_, t) {
		cin >> n;
		rep(i, n) {
			int a, b;
			cin >> a >> b;
			seg[i] = make_pair(a, b);
		}
		sort(seg, seg + n);

		int inf = 1000000001;
		int ans = 0, c = 0;
		int las = -inf;
		rep(i,n) {
			if (las < seg[i].first) {
				c++;
			}
			las = max(las, seg[i].second);
			last[i] = las;
			cnt[i] = c;
		}
	
		vector<int> vec;
		for (int i = n - 1; i >= 1; i--) {
			int num = cnt[i - 1];
			num += lower_bound(all(vec), last[i - 1], greater<int>()) - vec.begin();
			ans = max(ans, num);

			while (!vec.empty() && vec.back() <= seg[i].second) {
				vec.pop_back();
			}
			vec.push_back(seg[i].first);
		}
		ans = max<int>(ans, vec.size());

		cout << ans << endl;
	}
	return 0;
}