始まりと終わりを分けて要る部屋の数を数える

区間問題 161

研修の日程の並びから、同じ部屋で日が重ならないように割り当てるときに要る部屋の最少の数を求める。始まりの日と最終日を別々に並べて前から数えれば、同時に開いている研修の最大の数が分かります。

海外で定番の問題リスト 4 本には入っていません

問題

研修の日程が、[初日, 最終日] の組の並び plans で渡されます。日程は初日と最終日の両方を含み、研修は日程の間ずっと 1 つの部屋を使います。1 つの部屋で同じ日に 2 つの研修はできません。全部の研修に部屋を割り当てるとき、要る部屋の数の最少を返す関数を書いてください。

片方の最終日と、もう片方の初日が同じ 2 つの研修は、その日に重なるので同じ部屋に入れられません
plans は並べ替えられていません
どの組も、初日は最終日以下です
plans の長さは 1 以上 100000 以下、値はどれも 1 以上 1000000 以下です

入力と出力の例

例 1

3 日目は [1, 5]、[2, 3]、[3, 7] の 3 つが開かれているので、部屋が 3 つ要ります。

plans = [[1, 5], [2, 3], [3, 7], [6, 9], [9, 10]]

例 2

どの 2 つも日が重ならないので、1 つの部屋で足ります。

plans = [[7, 9], [1, 3], [4, 6]]

例 3

6 日目に 2 つの研修が開かれるので、部屋は 2 つ要ります。

plans = [[2, 6], [6, 8]]

面接での聞かれ方

面接では、会議室の予約の話として出されることが多いです。

「会議の時間帯の一覧があります。会議室はいくつあれば足りますか」
「終わりと始まりが同じ会議は、同じ部屋で続けてできますか」と聞くと、場面によって答えが変わります。この問題では日の単位なので、同じ日は重なるとします
書き終えたあとに「どの研修をどの部屋に入れるかも返してください」と、続きを聞かれることもあります

要る部屋の最少の数は、同じ日に開かれている研修の数の最大と同じです。言い換えてから考えると、方針が立てやすくなります。

ヒント

まだ開いていません

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

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

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に考えると、日ごとに開かれている研修を数え、その最大を取ることになります。ただ、日の値は 1000000 まであるので、全部の日を数えると研修の数より手間が大きくなることがあります。

段 2

開かれている研修の数が変わるのは、どれかの研修の初日と最終日の翌日だけです。研修を初日の順に見て、そのとき空いている部屋があれば使い、無ければ新しく足せばよさそうです。空いている部屋とは、入っていた研修の最終日が、いま見ている初日より前の部屋です。

段 3

どの部屋が空いたかは要らず、空いた部屋の数だけ分かれば足ります。そこで、初日だけの並びと最終日だけの並びを別々に並べ替えます。初日を小さい順に見て、最終日の並びの指す値がその初日より小さければ、その部屋は空いたので使い回し、指を 1 つ進めます。そうでなければ部屋を 1 つ足します。同じ日は重なるので、空いたと見るのは最終日が初日より小さいときだけです。

解答

Python

def min_groups(plans):
    starts = sorted(
        p[0] for p in plans
    )
    ends = sorted(
        p[1] for p in plans
    )
    rooms = 0
    j = 0
    for s in starts:
        if ends[j] < s:
            j += 1
        else:
            rooms += 1
    return rooms

JavaScript

function minGroups(plans) {
  const byNum = (p, q) => p - q;
  const starts = plans
    .map((p) => p[0])
    .sort(byNum);
  const ends = plans
    .map((p) => p[1])
    .sort(byNum);
  let rooms = 0;
  let j = 0;
  for (const s of starts) {
    if (ends[j] < s) {
      j++;
    } else {
      rooms++;
    }
  }
  return rooms;
}

Go

import "slices"

func minGroups(
	plans [][]int,
) int {
	n := len(plans)
	starts := make([]int, n)
	ends := make([]int, n)
	for i, p := range plans {
		starts[i] = p[0]
		ends[i] = p[1]
	}
	slices.Sort(starts)
	slices.Sort(ends)
	rooms, j := 0, 0
	for _, s := range starts {
		if ends[j] < s {
			j++
		} else {
			rooms++
		}
	}
	return rooms
}

JavaScript の sort は、比べる関数を渡さないと数を文字として並べます。[10, 9] が [10, 9] のまま残るので、(p, q) => p - q を必ず渡します。

計算量

時間は O(n log n) です。2 つの並べ替えが O(n log n)、その後のなめる処理は O(n) です
使う記憶は O(n) です。初日と最終日の並びを 1 つずつ持ちます
初日の順に並べ、使っている部屋の最終日を最小ヒープに入れる書き方でも同じ計算量です。どの部屋に入れたかまで返すときは、ヒープの書き方が向いています

よくある間違い

同じ日を重ならないと見る。空いたと見る式を ends[j] <= s と書くと、例 3 の [2, 6] と [6, 8] が同じ部屋に入り、答えが 1 になります。この問題では同じ日は重なるので < です
重なる組の数を数える。重なる 2 つの組を数えると、例 1 では [1, 5] と [2, 3]、[1, 5] と [3, 7]、[2, 3] と [3, 7]、[3, 7] と [6, 9]、[6, 9] と [9, 10] の 5 組になります。要るのは同じ日に開かれている数の最大です
初日の順に並べ、直前の研修とだけ比べる。直前と重なるかだけを見ると、例 1 の [3, 7] が [2, 3] と重なることは分かっても、[1, 5] もまだ部屋を使っていることを見落とします
最終日の並びの指を初日ごとに必ず進める。指を進めるのは部屋が空いたときだけです。毎回進めると、まだ使われている部屋を空いたと数えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def min_groups(plans: list[list[int]]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(min_groups([[1, 5], [2, 3], [3, 7], [6, 9], [9, 10]]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します