Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@Nary_

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

More than 1 year has passed since last update.

はじめに

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

問題

キーエンス プログラミングコンテスト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を更新する
出力して終了

まとめ

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

0
Help us understand the problem. What is going on with this article?
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
Nary_
理学療法士(Physical Therapist : PT)。 医療・ヘルスケアITに興味あり、python勉強中。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?