Codeforces ECR #004 : D. The Union of k-Segments

この回なんで書き忘れてたんだろう？
http://codeforces.com/contest/612/problem/D

問題

１次元の数直線上でN個の閉区間が与えられる。
各区間の端は整数の位置にある。

格子点のうち、M個以上の区間に含まれる点のみで構成される区間を列挙せよ。

解法

区間の開始及び終了の位置を座標順にソートして順に見ていくと、区間の開始・終了を経由した数により現在の位置が何個の区間に含まれるかわかる。
あとはM個以上の区間に含まれ出した点(求める区間の始点)と、M個以上の区間に含まれ終わった点(求める区間の終点)を列挙していけば良い。

int N,K;
vector<pair<int,int>> R;
set<int> S;
vector<pair<int,int>> E;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x>>y;
		E.push_back({x,0});
		E.push_back({y,1});
	}
	sort(ALL(E));
	
	int num=0;
	FORR(r,E) {
		if(r.second==0) {
			if(++num==K) R.push_back({r.first,0});
		}
		else {
			if(num--==K) R.back().second=r.first;
		}
	}
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d %d\n",r.first,r.second);
}

まとめ

Codeforcesっぽい定番問題だね。