[Python] 区間スケジューリング ABC103D

ABC103D

下図のようにすべて串刺しにするには、最小何本必要か、という問題である。

区間スケジューリング問題とは以下のような問題である:

M 個の区間が与えられ、どの 2 つの区間も時間帯を共有しないように最大個数の区間を選べ

蟻本の Greedy の章の最初にも載っている有名問題で、区間の終端でソートして Greedy にとっていけばよい。

実は今回の問題の答えは、区間スケジューリング問題の最適解と同じになる:

• まず区間スケジューリング問題の答えが k 個だった場合、その k 個は時間帯を共有しないので、それらを全部刺すには最低でも k 本の串が必要である (弱双対性)

逆に k 本の串があれば十分であることは、区間スケジューリング問題に対する貪欲法の動きを注意深く追うと理解することができる。具体的には、

• 区間スケジューリング問題で選ぶ k 個の区間に対して、その右端から串を刺していけば、ちょうど k 本の串ですべての区間を串刺しにできる (強双対性)

サンプルコード

from operator import itemgetter

n, m = map(int, input().split())

# 区間の終端でソート
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)