← 一覧へ戻る

区間の最大重なり数 LV4 ・ 40点

問題

数直線上に N 個の区間があります。i 番目の区間は s_i 以上 e_i 未満（半開区間 [s_i, e_i)）の範囲を表します。ある 1 点が最大でいくつの区間に同時に含まれるか、その最大数を求めてください。

例えば区間が [1, 5), [2, 6), [4, 8) のとき、点 4 はこの 3 つすべてに含まれるので、答えは 3 です。

制約

入力

入力は以下の形式で標準入力から与えられます。1 行目に区間の個数 N、続く N 行に各区間の s_i と e_i が与えられます。

N
s_1 e_1
s_2 e_2
...
s_N e_N

出力

1 点に同時に重なる区間の最大数を半角数字で出力してください。

入出力例

入力出力
3
1 5
2 6
4 8
3
3
1 2
2 3
3 4
1

💡 学習アドバイス

「同時に何個重なるか」は、区間どうしを総当たりで比べると大変ですが、イベントに分解して並べると一気に簡単になります（「いもす法」や「区間スケジューリング」に通じる考え方です）。

  1. 各区間を「開始（+1）」と「終了（-1）」の 2 つのイベントに分ける
  2. すべてのイベントを座標の小さい順に並べる（同じ座標なら、終了 -1 を開始 +1 より先に）
  3. 先頭から順にカウンタを増減させ、その途中の最大値を答えとする

半開区間 [s, e) では「同じ座標で終わる区間と始まる区間は重ならない」ので、終了を先に処理するのがコツです。並べ替え（ソート）と組み合わせる典型問題なので、考え方ごと身につけましょう。一度マスターすると応用範囲がとても広いテクニックです。

コーディング（ここで挑戦！）

下のエディタにコードを書き、「コンパイル・実行」で試し、「提出」で全テスト採点します。言語は C / C++ / Java から選べます。全テスト合格でこの問題はクリア（👑）です。

本番の編集・コンパイル・実行・採点は Exercode 上で行います。このページは予習・練習用です（実行は Wandbox の実コンパイラを利用）。