3 つの組に分けて新しい区間を差し込む

区間問題 158

始まりの順に並んだ重ならない予約の並びに、新しい予約を 1 本差し込み、重なる物をまとめた並びを返す。手前、重なる所、後ろの 3 つに分ければ、並べ替えずに前から 1 回なめるだけで済みます。

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

問題

ある会議室の予約済みの時間帯が、[始まり, 終わり] の組の並び booked で渡されます。そこへ新しい予約 extra ([始まり, 終わり] の組) を 1 本足します。重なっている時間帯と、ちょうど接している時間帯 (片方の終わりと、もう片方の始まりが同じ) を 1 つにまとめ、足した後の時間帯を始まりの小さい順に並べて返す関数を書いてください。

booked は始まりの小さい順に並んでいて、どの 2 つも重ならず、接してもいません
booked は空のこともあります
どの組も、始まりは終わり以下です
booked の長さは 0 以上 10000 以下、値はどれも 0 以上 100000 以下です
渡された booked の中身は書き換えないでください

入力と出力の例

例 1

[6, 10] は [5, 7] と [9, 12] の両方に重なるので、3 つが [5, 12] にまとまります。

booked = [[1, 3], [5, 7], [9, 12], [15, 18]] extra = [6, 10]

[[1, 3], [5, 12], [15, 18]]

例 2

どれとも重ならないときは、始まりの順の位置へそのまま入ります。

booked = [[4, 6], [10, 13]] extra = [7, 8]

[[4, 6], [7, 8], [10, 13]]

例 3

[4, 8] は、前の [2, 4] とも後ろの [8, 9] とも接しているので、全部が 1 つにまとまります。

booked = [[2, 4], [8, 9]] extra = [4, 8]

[[2, 9]]

面接での聞かれ方

面接では、区間をまとめる問題の続きとして出されることが多いです。

「並んだ予約の一覧に、新しい予約を 1 つ足してください。重なったらまとめてください」
「区間をまとめる問題と同じように、足してから並べ替えればいいですか」と聞くと、「並んでいることを使ってください」と返ってくるのがふつうです
「接している予約はまとめますか」と、端の扱いを聞かれることもあります

入力が並び済みで重ならないこと、接している物をまとめるかどうかを、書く前に確かめておきます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

素直に考えると、extra を booked の末尾に足し、始まりの順に並べ替えてから、区間をまとめる手順を回せば答えが出ます。ただ、並べ替えに O(n log n) かかり、booked がすでに並んでいることを使えていません。

段 2

booked を前から見ると、区間は 3 つの組に分かれます。extra の始まりより前で終わる物、extra と重なるか接する物、extra の終わりより後ろで始まる物です。並んでいて重ならないので、この 3 つは必ずこの順に、ひと続きで現れます。

段 3

1 つ目の組は、終わりが extra の始まりより小さい間、そのまま答えに写します。2 つ目の組は、始まりが extra の終わり以下の間、extra の始まりを小さい方へ、終わりを大きい方へ広げていきます。広げ終えた 1 本を答えに足し、残りの 3 つ目の組をそのまま写せば終わりです。接している物もまとめるので、比べるときは < と <= の向きに気をつけます。

解答

Python

def insert_interval(booked, extra):
    out = []
    s, e = extra
    i, n = 0, len(booked)
    while i < n and booked[i][1] < s:
        out.append(list(booked[i]))
        i += 1
    while i < n and booked[i][0] <= e:
        s = min(s, booked[i][0])
        e = max(e, booked[i][1])
        i += 1
    out.append([s, e])
    while i < n:
        out.append(list(booked[i]))
        i += 1
    return out

JavaScript

function insertInterval(
  booked, extra
) {
  const out = [];
  let [s, e] = extra;
  const n = booked.length;
  let i = 0;
  while (
    i < n && booked[i][1] < s
  ) {
    out.push([...booked[i]]);
    i++;
  }
  while (
    i < n && booked[i][0] <= e
  ) {
    s = Math.min(s, booked[i][0]);
    e = Math.max(e, booked[i][1]);
    i++;
  }
  out.push([s, e]);
  while (i < n) {
    out.push([...booked[i]]);
    i++;
  }
  return out;
}

Go

func insertInterval(
	booked [][]int, extra []int,
) [][]int {
	out := [][]int{}
	s, e := extra[0], extra[1]
	i, n := 0, len(booked)
	for i < n && booked[i][1] < s {
		b := booked[i]
		out = append(out,
			[]int{b[0], b[1]})
		i++
	}
	for i < n && booked[i][0] <= e {
		s = min(s, booked[i][0])
		e = max(e, booked[i][1])
		i++
	}
	out = append(out, []int{s, e})
	for ; i < n; i++ {
		b := booked[i]
		out = append(out,
			[]int{b[0], b[1]})
	}
	return out
}

どの言語も、答えに入れる組は新しく作っています。受け取った組をそのまま入れると、あとで呼び出し元が答えを書き換えたときに booked まで変わります。

計算量

時間は O(n) です。booked を前から 1 回なめるだけで、どの区間も 1 回しか見ません
使う記憶は O(n) です。答えの並びが最悪 n + 1 本の区間を持ちます
足してから並べ替える書き方は O(n log n) かかるので、並んでいることを使う分だけ速くなります

よくある間違い

接している区間を落とす。 1 つ目の組の条件を booked[i][1] <= s と書くと、例 3 の [2, 4] が「手前」に入り、[4, 8] とまとまりません。手前に入るのは終わりが extra の始まりより小さい物だけです
始まりを広げ忘れる。終わりだけを大きい方に取ると、例 1 で答えが [6, 12] になり、[5, 7] の 5 が消えます。重なった区間の始まりが extra より前のこともあります
広げた 1 本を足し忘れる。 2 つ目の組が空のとき (例 2) も、extra 自体は必ず答えに入ります。2 つ目のループの後で、条件なしに足します
booked が空のときに先頭を読む。 booked[0] を最初に読む書き方だと、空の並びで止まります。この解き方は、どのループも i < n で守っているので空でも動きます

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

main.py

def insert_interval(booked: list[list[int]], extra: list[int]) -> list[list[int]]:
    """
    Goal: 何を返すか

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

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

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


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

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