Algorithm | 区間スケジューリング問題をPython3で解説（例題あり）

区間スケジューリング問題とは

区間スケジューリング問題とは、それぞれの区間が重複せず、それぞれの区間の数を最大化するためにはどうすればよいかを考える問題である。

具体的には次のように行う。

1. 区間の右端の数字が小さい順番になるように、昇順に並び替えをする
2. 並び替えした区間を順番に見ていく
3. 「その区間の左端」と「ひとつ前の区間の右端」とを比較する
4. 「その区間の左端」の数字が大きければ、その区間を採用し、右端の値を「ひとつ前の区間の右端」の値とする. 「その区間の左端」の数字が小さければ、区間が重複しているので、採用しない.
5. 3、4を繰り返す

このようにすることで、区間の数の最大値を求めることができる。

区間スケジューリング問題を見分けるポイント

区間スケジューリング問題を見分けるには、以下の言葉に注目すると良い。

・数直線上
・それぞれaからbまでの範囲をとる
・重複してはいけない
・最大でX個とれるか

区間スケジューリング問題の基本問題

典型アルゴリズム問題集 B - 区間スケジューリング問題

answer

def main():
    n = int(input())
    ablist = [list(map(int, input().split())) for _ in range(n)]

    sort_ablist = sorted(ablist, key=lambda x: (x[1], x[0])) # 右端の値に対して昇順に並び替え

    ans = 0
    x = -(10**10) # はじめの右端の値は-∞

    for a, b in sort_ablist: # 並び替えした値それぞれについて
        if x-1 < a: # 「その区間の左端」の数字が大きければ
            ans += 1 # 値を採用
            x = b # 右端の値を「ひとつ前の区間の右端」の値とする

    print(ans)

if __name__ == '__main__':
    main()

区間スケジューリング問題そのものの問題。今回の内容を理解するためのに、うってつけの問題である。

区間スケジューリング問題を用いた例題

例題: ABC103 D - Islands War

answer

def main():
    n, m = map(int, input().split())
    ablist = [list(map(int, input().split())) for _ in range(m)]

    sort_ablist = sorted(ablist, key=lambda x: (x[1], x[0]))

    ans = 0
    x = -(10**6)

    for a, b in sort_ablist:
        if x-1 < a:
            ans += 1
            x = b

    print(ans)


if __name__ == '__main__':
    main()

例題: ABC230 D - Destroyer Takahashi

answer

def main():
    n, d = map(int, input().split())
    lrlist = [list(map(int, input().split())) for _ in range(n)]

    sort_lrlist = sorted(lrlist, key=lambda x: (x[1], x[0]))

    ans = 0
    x = -(10**10)

    for l, r in sort_lrlist:
        if x + d - 1 < l:
            ans += 1
            x = r

    print(ans)


if __name__ == '__main__':
    main()

例題: キーエンスプログラミングコンテスト2020(ARC like) B - Robot Arms

answer

def main():
    n = int(input())
    xllist = [list(map(int, input().split())) for _ in range(n)]

    lrlist = []

    for x, l in xllist:
        lr = [x-l, x+l]
        lrlist.append(lr)

    sort_lrlist = sorted(lrlist, key=lambda x: (x[1], x[0]))

    ans = 0
    now = -(10**10)

    for l, r in sort_lrlist:
        if now-1 < l:
            ans += 1
            now = r

    print(ans)


if __name__ == '__main__':
    main()

まとめ

問題に慣れてしまえば、実装はそこまで難しくはない。問題文をみて、いかにして気付けるかが大切である。