キーエンスプログラミングコンテスト2020 B問題区間スケジューリングを学ぶ

貪欲法を中心に学んでいる中、区間スケジューリングという手法についても学びたいと思い、定番と言われている問題を解きました。
区間スケジューリングを知らない状態で挑んでみましたが、やはり解けず、区間スケジューリングの手法を調べて解けました。

ロボットの腕がN台あって、腕の長さと置いてある位置が指定されています。
腕が届く範囲は置いてある位置から、 $X_i$ プラスマイナス $L_i$ の範囲。
範囲がかぶらないように置ける最小の台数を求める問題です。

まず範囲がかぶらない状態を絵にします。

黄色い線に被らない黒い線のパターンは2つです。
黄色い線の左端（下限）が黒い線の右端（上限）よりも右にあるか、黄色い線の右端（上限）が黒い線の左端（下限）よりも左にあるか。

何も工夫しない場合、2つの区間がかぶっていないか調べるには2つのパターンの内のどちらに該当するか調べることになります。
そしてこの問題では複数の離れた区間があるので、それぞれの区間について調べる必要があります。

区間スケジューリングの工夫ポイントとしては、右端（上限）の位置の小さい順にあらかじめソートすることです。
そして調べている区間で一番右端になっている範囲の位置を記録します。

そうすると調べるパターンとしては、絵の中で右側の黒い線になっているかどうかだけチェックすれば良いことになります。
右端の位置の小さい順にソートされていて、これまで調べた区間で一番右端の位置が記録されているので、
調べる区間の左端がこれまで調べた区間の一番右端の位置の右側にあるかどうかを確認します。

ソースコードは以下のようになります。

N = int(input())
xl_list = []
for _ in range(N):
    xi, li = list(map(int, input().split()))
    xl_list.append([xi - li, xi + li])

sorted_xl = sorted(xl_list, key=lambda x: x[1])
upper = -10 ** 9 - 1
ans = 0
for xl in sorted_xl:
    # かぶっていたら次のループ
    if upper > xl[0]:
        continue
    ans += 1
    upper = max(upper, xl[1])

print(ans)

何も調べないで頭を悩ませたおかげなのか、調べた後に目から鱗が落ちる感覚が強く、印象が強く残った気がします。