【AtCoder版！蟻本】キーエンスプロコン2020 B - Robot Arms【区間スケジューリング】

AtCoder版！蟻本の区間スケジューリングの例題としてあげられているキーエンスプロコン2020 B - Robot ArmsをPythonで解いていきます。

リンク

B - Robot Arms

キーエンスプロコン2020 B - Robot Arms

問題文

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

制約

・1≤N≤100,000
・0≤Xi≤10^9 ( 1 ≤ i ≤ N )
・1≤Li≤10^9 ( 1 ≤ i ≤ N )
・i≠j のとき、Xi≠Xj
・入力値はすべて整数である。

解答例

n = int(input())

X = []
L = []
for i in range(n):
    x, l = map(int,input().split())
    X.append(x)
    L.append(l)

P = []

for i in range(n):
    s = X[i] - L[i]
    t = X[i] + L[i]
    P.append([s,t])

P.sort(key=lambda x:x[1])

res = 0
tmp = -1e9
for i in range(n):
    if tmp <= P[i][0]:
        res += 1
        tmp = P[i][1]

print(res)

解説

直線状にN台のロボットが設置されており、Liだけ腕を伸ばすことができます。
腕の届く範囲が共通部分を持たないようにロボットを取り除くとき、残すことのできる最大の台数を答える問題です。

i台目のロボットの腕の届く範囲の最小値をs、最大値をtとして配列Pに格納していき、格納後はtについてソートします。

次にソート済みのロボット稼働範囲をループで調べていきました。
tmpが現在残っているロボット稼働範囲の最大値です。
このtmpよりi番目の稼働範囲 最小値が大きいとき、このロボットを残すことができますのでresに1を足し、tmpをこのロボット稼働範囲の最大値に更新します。

このループを抜けた後にresを出力すればOKでした！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク