2 本の指で 2 人とも空いている日を求める

区間問題 160

2 人それぞれの、日の順に並んだ休みの範囲の一覧から、2 人とも休みの範囲を並べて返す。両方の並びに指を 1 本ずつ置き、先に終わる方の指を進めれば、1 回なめるだけで全部の重なりが拾えます。

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

問題

2 人の休みの日の範囲が、[初日, 最終日] の組の並び a と b で渡されます。範囲は初日と最終日の両方を含みます。2 人とも休みの日の範囲を、初日の小さい順に並べて返す関数を書いてください。

a も b も、初日の小さい順に並んでいて、同じ並びの中のどの 2 つも重ならず、接してもいません
片方の最終日と、もう片方の初日が同じなら、その 1 日は 2 人とも休みです。[t, t] の 1 日の範囲として返します
a と b は、どちらも空のことがあります。2 人とも休みの日が無ければ、空の並び [] を返します
どの組も、初日は最終日以下です
a と b の長さはどちらも 0 以上 1000 以下、値はどれも 0 以上 1000000000 以下です

入力と出力の例

例 1

b の [3, 9] は a の 2 つの範囲にまたがるので、重なりが 2 つできます。

a = [[1, 4], [8, 12], [15, 20]] b = [[3, 9], [11, 16]]

[[3, 4], [8, 9], [11, 12], [15, 16]]

例 2

a の最終日と b の初日が同じ 6 日なので、その 1 日だけが重なります。

a = [[2, 6]] b = [[6, 10]]

[[6, 6]]

例 3

b の範囲は、a の 2 つの範囲のちょうど間にあり、どちらとも重なりません。

a = [[1, 3], [7, 9]] b = [[4, 6]]

[]

面接での聞かれ方

面接では、予定を合わせる話として出されることが多いです。

「2 人の空いている時間の一覧があります。2 人とも空いている時間を全部出してください」
「一覧は並んでいますか」と聞くと、「並んでいて、同じ人の中では重なりません」と返ってくるのがふつうです
書き終えたあとに「3 人以上ならどうしますか」と、続きを聞かれることもあります

両端を含むかどうかで、例 2 の 1 日の扱いが変わります。書く前に確かめておきます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

素直に考えると、a の範囲と b の範囲の組を全部調べ、重なる所を集めてから並べ替えることになります。長さを m と n とすると O(mn) かかり、並んでいることを使えていません。

段 2

2 つの範囲 [s1, e1] と [s2, e2] の重なりは、初日が max(s1, s2)、最終日が min(e1, e2) の範囲です。初日が最終日以下なら重なりがあり、そうでなければありません。重なりの有無と中身は、この 2 つの値だけで決まります。

段 3

両方の並びの先頭に指を 1 本ずつ置き、指した 2 つの重なりを調べて、あれば答えに足します。そのあと、最終日が早い方の指を 1 つ進めます。最終日が早い方の範囲は、もう片方の並びの後ろの範囲とは重ならないからです。どちらかの指が並びの外へ出たら終わりです。答えは初日の順に自然に並びます。

解答

Python

def interval_intersections(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        s = max(a[i][0], b[j][0])
        e = min(a[i][1], b[j][1])
        if s <= e:
            out.append([s, e])
        if a[i][1] < b[j][1]:
            i += 1
        else:
            j += 1
    return out

JavaScript

function intervalIntersections(
  a, b
) {
  const out = [];
  let i = 0;
  let j = 0;
  while (
    i < a.length && j < b.length
  ) {
    const s = Math.max(
      a[i][0], b[j][0],
    );
    const e = Math.min(
      a[i][1], b[j][1],
    );
    if (s <= e) {
      out.push([s, e]);
    }
    if (a[i][1] < b[j][1]) {
      i++;
    } else {
      j++;
    }
  }
  return out;
}

Go

func intervalIntersections(
	a, b [][]int,
) [][]int {
	out := [][]int{}
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		s := max(a[i][0], b[j][0])
		e := min(a[i][1], b[j][1])
		if s <= e {
			out = append(out,
				[]int{s, e})
		}
		if a[i][1] < b[j][1] {
			i++
		} else {
			j++
		}
	}
	return out
}

最終日が同じときは b の指を進めています。どちらを進めても、次の回で残った方の範囲は相手の次の範囲と重ならないことが分かるだけなので、答えは変わりません。

計算量

時間は O(m + n) です。1 回まわるたびにどちらかの指が 1 つ進むので、まわる回数は m + n 以下です
使う記憶は、答えの並びを除けば O(1) です。答えの並びは最悪 m + n - 1 本の範囲を持ちます
全部の組を調べる書き方の O(mn) より速いのは、並んでいて重ならないことを使っているからです

よくある間違い

1 日だけの重なりを落とす。重なりがある条件を s < e と書くと、例 2 の [6, 6] が答えに入りません。両端を含むので s <= e です
重なったときに両方の指を進める。例 1 で [1, 4] と [3, 9] が重なったあと両方を進めると、[3, 9] と [8, 12] の重なり [8, 9] を落とします。進めるのは最終日が早い方だけです
初日の早い方の指を進める。 a = [[1, 10]]、b = [[2, 3], [5, 6]] で初日の早い [1, 10] を進めると、a が尽きて [5, 6] を落とします。範囲が「もう要らない」と分かるのは、最終日で比べたときだけです
空の並びを特別扱いし忘れる。先頭を読んでから回す書き方だと、a か b が空のときに止まります。この解き方は、ループの条件で両方の長さを見ているので空でも動きます

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

main.py

def interval_intersections(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
    """
    Goal: 何を返すか

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

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

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


# 「実行」を押すと、この行の結果が出ます
print(interval_intersections([[1, 4], [8, 12], [15, 20]], [[3, 9], [11, 16]]))

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