同時に使われる会議室の数

並べ替えと貪欲
問題 12
ふつう
目安 31 分

会議室の予約の開始と終了の時刻の一覧から、同じ時刻に使われている予約の最大の数を求める。予約どうしを全部比べず、時刻を並べ替えて順に数える練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 3 秒までです。

問題

ある会社の会議室の予約が N 件あります。予約 i は、時刻 s_i に始まり時刻 e_i に終わります。時刻は、ある日の 0 時から数えた分です (翌日より先の予約もあります)。予約 i は、時刻 t が s_i 以上で e_i より小さいときに会議室を使っています。終わる時刻ちょうどには、もう使っていません。このため、ある予約が終わる時刻と、別の予約が始まる時刻が同じなら、2 つは重ならず、1 つの会議室を続けて使えます。

同じ時刻に使われている予約の数の最大を出力してください。これは、全部の予約を受けるのに要る会議室の数でもあります。

入力の形式

N
s_1 e_1
s_2 e_2
...
s_N e_N

1 行目に予約の数 N、2 行目から N 行は、1 行に 1 つの予約の開始の時刻 s_i と終了の時刻 e_i が半角の空白 1 つで区切られて並びます。予約は時刻の順に並んでいるとは限りません。

出力の形式

同じ時刻に使われている予約の数の最大を 1 行に出力します。

制約

N は 1 以上 200000 以下です
s_i と e_i は、0 以上 1000000 以下の整数です
開始は終了より前です (s_i は e_i より小さいです)

入力と出力の例

例 1

9 時 (540 分) から 10 時、9 時 30 分から 11 時、10 時から 10 時 30 分、10 時 15 分から 12 時の 4 件です。10 時 15 分から 10 時 30 分までは、2 件目、3 件目、4 件目の 3 件が同時に使われています。1 件目は 10 時ちょうどに終わり、3 件目は 10 時ちょうどに始まるので、この 2 つは重なりません。

入力

出力

例 2

前の予約が終わる時刻ちょうどに次の予約が始まる 3 件です。どの 2 つも重ならないので、1 つの会議室で足ります。

入力

出力

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

開始の時刻の並び starts と、終了の時刻の並び ends を、それぞれ早い順に並べ替えます。starts を前から見て、k 番目 (0 から数える) の開始の時刻 t で、ends の中の t 以下の個数 j を、前の続きから数え進めます。t には k + 1 件が始まっていて、j 件が終わっているので、使われているのは k + 1 - j 件です。終了の時刻が t ちょうどの予約は t 以下として終わった側に数えるので、終わりと始まりが同じ時刻の 2 件は重なりません。同じ時刻に始まる予約が複数あるときは、その最後の 1 件で全部を数えた値になり、最大は正しく取れます。

Python

import sys

data = sys.stdin.read().split()
n = int(data[0])
starts = sorted(map(int, data[1:1 + 2 * n:2]))
ends = sorted(map(int, data[2:2 + 2 * n:2]))

best = 0
j = 0
for k in range(n):
    t = starts[k]
    while ends[j] <= t:
        j += 1
    if k + 1 - j > best:
        best = k + 1 - j

print(best)

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const starts = new Int32Array(n);
const ends = new Int32Array(n);
for (let i = 0; i < n; i++) {
  starts[i] = data[1 + 2 * i];
  ends[i] = data[2 + 2 * i];
}
starts.sort();
ends.sort();

let best = 0;
let j = 0;
for (let k = 0; k < n; k++) {
  const t = starts[k];
  while (ends[j] <= t) j++;
  if (k + 1 - j > best) best = k + 1 - j;
}

console.log(best);

計算量

時間は O(N log N) で、ほとんどが 2 つの並べ替えです。数え進める部分は、k も j も前にしか進まないので、合わせて 2N 回ほどです。予約ごとに、その開始の時刻に使われている予約をほかの全部から数える書き方は O(N × N) で、N が 20 万の入力では 400 億回の比べになり、時間切れになります。

よくある間違い

終わる時刻と始まる時刻が同じ 2 件を、重なっていると数える。終了の時刻が t 以下の予約は、t にはもう使っていません (< ではなく <= で数え進めます)
「ほかの予約と重なる件数」の最大を答えにする。予約 A が B とも C とも重なっていても、B と C が重なっていなければ、同時に使われるのは 2 件です
開始と終了を 1 つの並びにまとめて並べ替えるとき、同じ時刻の開始と終了の順番を決めずに並べる。同じ時刻なら終了を先に処理しないと、重ならない 2 件を重なったと数えます
JavaScript で Array の sort() を引数なしで呼ぶ。数ではなく文字として並ぶので、1000 が 600 より前に来ます。普通の配列なら sort((a, b) => a - b) と書きます (この解答の Int32Array の sort() は数として並びます)

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
n = int(data[0])
starts = list(map(int, data[1:1 + 2 * n:2]))
ends = list(map(int, data[2:2 + 2 * n:2]))

# ここから書く

入力

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します