Help us understand the problem. What is going on with this article?

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

はじめに

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

問題

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

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

回答

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を更新する
出力して終了

まとめ

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした