問題
会議室の[始まり, 終わり] のintervals で
intervalsは並べ替えられていません - どの
組も、 始まりは 終わり以下です。 始まりと 終わりが 同じ組もあります intervalsの長さは 1 以上 10000 以下、 値は どれも 0 以上 10000 以下です
入力と出力の例
例 1
[1, 4] と [3, 6] が[10, 11] は [9, 12] の
入力
intervals = [[9, 12], [1, 4],
[3, 6], [10, 11]]出力
[[1, 6], [9, 12]]例 2
終わりと
入力
intervals = [[2, 5], [5, 8]]出力
[[2, 8]]例 3
あとから
入力
intervals = [[1, 10], [2, 3],
[4, 8]]出力
[[1, 10]]面接での聞かれ方
面接では、
- 「区間の
配列が あります。 重なっている ものを まとめてください」 - 「並べ替え済みですか」と
聞き返すと、 「いいえ」と 返ってくるのが ふつうです - 書き終えた
あとに 「並べ替えなしで できますか」 「区間が 次々に 届くなら どうしますか」と、 続きを 聞かれる こともあります
接している[2, 5] と [5, 8] を
アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。
まず
段 1
素直に
段 2
始まりの
段 3
並べ替えた
解答
Python
Python
def merge_intervals(intervals):
items = sorted(
intervals,
key=lambda iv: iv[0],
)
out = [list(items[0])]
for s, e in items[1:]:
last = out[-1]
if s > last[1]:
out.append([s, e])
elif e > last[1]:
last[1] = e
return outJavaScript
JavaScript
function mergeIntervals(
intervals
) {
const items = [...intervals];
items.sort(
(p, q) => p[0] - q[0],
);
const out = [[...items[0]]];
const rest = items.slice(1);
for (const [s, e] of rest) {
const last = out.at(-1);
if (s > last[1]) {
out.push([s, e]);
} else if (e > last[1]) {
last[1] = e;
}
}
return out;
}Go
Go
import "slices"
func mergeIntervals(
intervals [][]int,
) [][]int {
items := slices.Clone(
intervals,
)
slices.SortFunc(items, func(
p, q []int,
) int {
return p[0] - q[0]
})
f := items[0]
out := [][]int{{f[0], f[1]}}
for _, iv := range items[1:] {
s, e := iv[0], iv[1]
last := out[len(out)-1]
if s > last[1] {
pair := []int{s, e}
out = append(out, pair)
} else if e > last[1] {
last[1] = e
}
}
return out
}どの[s, e] のintervals まで
計算量
- 時間は O(n log n) です。
並べ替えが O(n log n)、 その 後の なめる 処理は O(n) なので、 並べ替えが 全体を決めます - 使う
記憶は O(n) です。 並べ替えた 写しと 答えの 並びが、 どちらも 最悪 n 個の 区間を持ちます - 区間が
始まりの 順で 届くと 分かっているなら、 並べ替えが 要らなくなり、 時間は O(n) に 下がります
よく
- 並べ替えを忘れる。
例 1 を 並べ替えずに なめると、 [9, 12]の次に [1, 4]が来て、 どちらとも 重ならないまま 答えが 4 つになります - 終わりを
上書きする。 last[1] = eと書くと、 例 3 で [1, 10]の後に [2, 3]が来た とき、 終わりが 3 に 縮みます。 次の 終わりの 方が 大きい ときだけ 伸ばします - 接している
場合を落とす。 重ならない 条件を s >= last[1]と書くと、 例 2 の [2, 5]と[5, 8]がまとまりません。 重ならないのは s > last[1]のときだけです - 入力の
組を そのまま 答えに入れる。 Python で out = [items[0]]やout.append(iv)と書くと、 終わりを 伸ばした ときに 呼び出し元の 並びの 中身まで 変わります。 面接では 「入力を 壊さないように 新しい 組を 作ります」と 一言添えます - 終わりで
並べ替える。 終わりの 順に 並べると、 [[1, 10], [2, 3]]が[2, 3]から始まり、 [1, 10]を足すときに 始まりが 前へ 戻るのを 扱えません
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「全部の
組で 重なりを 調べると O(n²) かかり、 まとめた 後に また重なる 場合も 追い かける ことになります。 始まりの 順に 並べ替えれば、 重なりうるのは 直前に まとめた 区間だけなので、 前から 1 回なめて、 重なれば 終わりを 大きい方に 伸ばし、 重ならなければ 新しく 足すだけで 済みます。 並べ替えが O(n log n) で 全体も それで 決まり、 記憶は 答えと 写しの 分の O(n) です。」
書き終えたら、
「例 1 を
並べ替えると [1, 4]、[3, 6]、[9, 12]、[10, 11]の順です。 [3, 6]は 3 が 4 以下なので重なり、 終わりを 6 に 伸ばします。 [9, 12]は 9 が 6 より大きいので 新しく 足します。 [10, 11]は重なりますが、 終わりは 12 と 11 の 大きい方の 12 のままです。 答えは [[1, 6], [9, 12]]です。」