区間スケジューリング 学習メモ ～by python～

はじめに

貪欲法　区間スケジューリング問題についての学習メモ

問題

キーエンス　プログラミングコンテスト2020の"B問題　Robot Arms"

始点、終点が決まっているものについて、できる限り多く選択していく問題（区間スケジューリング問題）
貪欲法で解いていく
基本方針は選べるロボットの中で終点が最小のものを選んでいくこと

回答

N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]

R=[]
for i in range(N):
    a=max(0,XL[i][0]-XL[i][1])
    b=XL[i][1]+XL[i][0]
    R.append([b,a])
R.sort()

ans=0
con_l=0
for i in range(N):
    if con_l <= R[i][1]:
        ans += 1
        con_l = R[i][0]
print(ans)

解説

①入力

N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]

Nはロボットの個数
XLは座標Xと腕の長さLのリスト

②リストの編集

ロボットの腕の始点(a)と終点(b)を保存するリスト(R)を作成する

R=[]
for i in range(N):
    a=max(0,XL[i][0]-XL[i][1])
    b=XL[i][1]+XL[i][0]
    R.append([b,a])
R.sort()

リストRは終点昇順でソートしておく

③区間スケジューリング＆出力

ans=0
con_l=0
for i in range(N):
    if con_l <= R[i][1]:
        ans += 1
        con_l = R[i][0]
print(ans)

ansは選んだロボットの個数
con_lは最後に選んだロボットの腕の終点

forループ内の処理は最後に選んだロボットの終点(con_l)より大きい始点(R[i][1])を持つロボットを貪欲的に探索するようになっている
Rは終点昇順でソートしてあるため、探索していく中で最小の終点のものを常に選択するようになっている
見つかるたびにansに+1してcon_lを更新する
出力して終了

まとめ

典型的な区間スケジューリング問題であった