AtColor [AtCoder Beginner Contest 014 C]

atcoder.jp

区間が N 個与えられる。
最も多くの区間に被覆されている値の、その区間の数を求めよ、という問題です。

解説にあるように、imos法を使うみたいです。
imos法は累積和を応用したアルゴリズムで、実装はとても簡単です。

区間の最小値～最大値に対応できる長さの配列 A を用意します。
区間 a,b で被覆するときは、A[a]++, A[b+1]++ とします。
全ての区間を被覆し終えたら、配列 A の累積和をとります。
その後、配列内にある値 A[i] が、i が被覆された回数となります。

void solve () {

	int n = nextInt();
	int[] ar = new int[1000002];

	//区間の前処理をする
	for (int i=0; i<n; i++) {
		ar[nextInt()]++;
		ar[nextInt()+1]--;
	}

	//累積和をとる
	cumsumIntArray(ar);

	//配列内の最大値が答え
	out.println(maxIntArray(ar));

}