貪欲法は「よさそう」で決めない

局所的に選んだ手が最適解を壊さないことを示します。典型は、区間を終了時刻の早い順に選ぶ方法です。

言語：Python / 計算量：O(N log N)

前提：ソートで順序を作る

考え方

1. 選択規則を1つ決めます。
2. 最適解の最初の選択と入れ替えて悪化しないか考えます。
3. 入れ替え後に残りへ同じ議論を繰り返します。

具体例

[0,3),[1,2),[2,4) では終了が早い [1,2) を選ぶと [2,4) も選べます。開始が早い順だと1個で終わることがあります。

実装

intervals = [(0,3), (1,2), (2,4)]
end = -10**18
ans = 0
for l, r in sorted(intervals, key=lambda p:p[1]):
    if l >= end:
        ans += 1
        end = r
print(ans)

注意する条件

価値付き区間の最大価値にはこの規則は使えません。個数を最大にする問題との違いです。

確認問題

上の3区間から重ならず選べる最大個数は？

実装課題

N 個の半開区間 [L,R) から重ならない最大個数を求める。1 ≤ N ≤ 200000、0 ≤ L < R ≤ 10^9。

入力:
3
0 3
1 2
2 4
出力:
2

n = int(input())
a = [tuple(map(int,input().split())) for _ in range(n)]
end = -1
ans = 0
for l, r in sorted(a, key=lambda p:p[1]):
    if l >= end:
        ans += 1
        end = r
print(ans)

読了の記録・下書き・メモへ