終わりの順の貪欲で重なりを消す

区間問題 159

1 台の機械に入った作業の時間帯の並びから、残りが重ならないように外す本数の最少を求める。終わりの早い順に並べ、残せる物を前から選んでいくと、外す本数が最も少なくなります。

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

問題

1 台の印刷機に入った仕事の時間帯が、[始まり, 終わり] の組の並び jobs で渡されます。印刷機は同時に 1 つの仕事しかできません。いくつかの仕事を外して、残りのどの 2 つも重ならないようにしたいとき、外す仕事の数の最少を返す関数を書いてください。

片方の終わりと、もう片方の始まりが同じ (ちょうど接している) 2 つは、重ならないと見ます
jobs は並べ替えられていません
どの組も、始まりは終わりより小さいです
jobs の長さは 1 以上 100000 以下、値はどれも -50000 以上 50000 以下です

入力と出力の例

例 1

[2, 3] と [4, 7] を残し、[1, 5] と [6, 8] を外せば重なりが消えます。3 つ残す方法はありません。

jobs = [[1, 5], [2, 3], [4, 7], [6, 8]]

例 2

どの 2 つも接しているだけなので、外す必要はありません。

jobs = [[3, 5], [5, 9], [0, 3]]

例 3

長い [0, 10] 1 つを外せば、短い 3 つが残せます。

jobs = [[0, 10], [1, 2], [3, 4], [5, 6]]

面接での聞かれ方

面接では、予定の調整の話として出されることが多いです。

「重なっている会議があります。いくつ取り消せば重ならなくなりますか。最少で答えてください」
「接している会議は重なりますか」と聞き返すと、「重ならないとします」と返ってくるのがふつうです
書き終えたあとに「なぜ終わりの順で選ぶと最少になるのですか」と、理由を聞かれることもあります

「外す最少」は「残せる最多」と同じ問題です。言い換えてから考えると、方針が立てやすくなります。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

素直に考えると、外す仕事の組み合わせを全部試し、残りが重ならない物のうち外す数が最も少ない物を探すことになります。組み合わせは 2 の n 乗あるので、n が大きいと終わりません。

段 2

外す数を最少にするのは、残す数を最多にするのと同じです。残す仕事を 1 つ選ぶとき、終わりが最も早い仕事を選ぶと、後ろに使える時間が最も多く残ります。例 3 の [0, 10] のように、早く始まっても遅く終わる仕事を選ぶと、後ろの仕事を多く締め出してしまいます。

段 3

仕事を終わりの早い順に並べ、最後に残した仕事の終わりを 1 つ持ちます。次の仕事の始まりがその終わり以上なら、重ならないので残し、終わりを更新します。そうでなければ外して数えます。接している物は重ならないので、比べるのは >= です。

解答

Python

def remove_overlaps(jobs):
    items = sorted(
        jobs,
        key=lambda iv: iv[1],
    )
    removed = 0
    end = items[0][1]
    for s, e in items[1:]:
        if s >= end:
            end = e
        else:
            removed += 1
    return removed

JavaScript

function removeOverlaps(jobs) {
  const items = [...jobs];
  items.sort(
    (p, q) => p[1] - q[1],
  );
  let removed = 0;
  let end = items[0][1];
  const rest = items.slice(1);
  for (const [s, e] of rest) {
    if (s >= end) {
      end = e;
    } else {
      removed++;
    }
  }
  return removed;
}

Go

import "slices"

func removeOverlaps(
	jobs [][]int,
) int {
	items := slices.Clone(jobs)
	slices.SortFunc(items, func(
		p, q []int,
	) int {
		return p[1] - q[1]
	})
	removed := 0
	end := items[0][1]
	for _, iv := range items[1:] {
		if iv[0] >= end {
			end = iv[1]
		} else {
			removed++
		}
	}
	return removed
}

どの言語も、写しを並べ替えています。受け取った jobs をその場で並べ替えると、呼び出し元の並びの順まで変わります。

計算量

時間は O(n log n) です。並べ替えが O(n log n)、その後のなめる処理は O(n) なので、並べ替えが全体を決めます
使う記憶は O(n) です。並べ替えた写しが n 個の組を持ちます
終わりが同じ仕事が並んだときの順は、答えに関わりません。どちらを先に残しても、次に比べる終わりは同じだからです

よくある間違い

始まりの順に並べて、最初の物を残す。例 3 を始まりの順に見ると、最初の [0, 10] を残してしまい、残り 3 つを全部外して答えが 3 になります。残す物は終わりの早い順に選びます
接している物を重なりと数える。比べる式を s > end と書くと、例 2 の [0, 3] と [3, 5] が重なると見られ、答えが 0 になりません
外した仕事で終わりを更新する。外すと決めた仕事の終わりで end を書き換えると、すでに残した仕事との重なりを見落とします。end を変えるのは残したときだけです
重なる組の数を数える。重なっている 2 つの組の数を返すと、例 3 では [0, 10] が 3 つと重なるので 3 になります。1 つ外せば 3 組の重なりが同時に消えることがあります

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

main.py

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

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

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

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


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

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