Pythonで区間スケジューリング問題を解いてみる-キーエンスプロコン2020

この記事では区間スケジューリング問題をPythonを利用して解いていきます。

区間スケジューリング問題はソートと貪欲法を利用することによって解くことができます。

貪欲法を知らない方はまずこちらの記事をお読みください。
nashidos.hatenablog.com

例題

atcoder.jp

問題文

ある工場では、 数直線上に N 個のロボットが設置されています。 ロボット i は座標 Xi に設置されており、数直線の正負の方向にそれぞれ長さ Liの腕を伸ばすことができます。
これらのロボットのうちいくつか (0個以上) を取り除き、 残ったどの 2 つのロボットについても、腕が動く範囲が共通部分を持たないようにしたいと思います。 ただし、各 i (1≤i≤N) に対して、 ロボット i の腕が動く範囲とは 数直線上の座標が Xi−Li より大きく Xi+Li未満の部分を指します。
取り除かずに残せるロボットの個数の最大値を求めてください。

制約

1≤N≤100,000
0≤Xi≤109(1≤i≤N)
1≤Li≤109(1≤i≤N)
i≠jのとき、Xi≠Xj
入力値はすべて整数

実装

方針としては、リストに始点と終点を格納し、終点でソートします。

その後は貪欲に範囲が重なっていたら取り除いていけばOKです。

n = int(input())
ls = []
for i in range(n):
    x,l = map(int,input().split())
    ls.append([x-l,l+x])
    
ls = sorted(ls, key=lambda x: x[1])
ans = n

for i in range(1,n):
    if ls[i][0] < ls[i-1][1]:
      ls[i][1] = ls[i-1][1]
      ans -=1
        
print(ans)

まとめ

実装自体はあまり難しくないですが、区間スケジューリング問題を知らないとなかなか解きにくい問題だったかもしれないですね。

おわり。