キーエンスプログラミングコンテスト2020 B - Robot Arms

昨日のキーエンスプログラミングコンテストでは撃沈した。Ｂ問題が解けなかった。 解説を見ると，どうも区間スケジューリングと呼ばれる典型問題らしい。また，Twitterによると蟻本にも書いてあるとのこと。
蟻本は多少読んだけど，まだ自分が読んでいない部分だったのかなと思って調べたら，がっつり以前読んでいた部分であった（かなしい）。
ということで少し復習してみた。

区間スケジューリング問題とは（蟻本）

• ｎ個の仕事がある

• 各仕事の開始時刻と，終了時刻が与えられる

• 各仕事について，参加するかどうか選択する

• 参加する場合は，開始時刻から終了時刻までその仕事しかできない

• 同一時刻に複数の仕事することはできない（ある仕事の終了時刻と，別の仕事の開始時刻が重なってもいけない）

このとき，最大で何個の仕事に参加可能か。 　　　　

解法　選べる仕事の中で，終了時刻が一番早いものを選び続ければよい（貪欲法）　　　　

それっぽい説明

上の図のような状態だとする（線分1本1本が仕事を表す）。また，これより左側（早い時刻）では最適な仕事が選ばれているとする。このときに選ぶべき仕事を考える。

この図よりも右側において，より多くの仕事を選ぶことができる仕事が最適である。それは一番上の線分で表される仕事である。なぜなら右側の区間を一番長く残せるからである。

この図の左側では最適に選んでいるので，残りの時間（右側）をいかに長くできるかを考えれば良いという点がポイントだと思っている。

今回の問題

B - Robot Arms

注意点 ロボットのアームはより大きく未満である。と書いてあるので区間の端は重なっても良いということになる。また，ロボットのアームが一番左に行くのはのときにとなる場合である。
このことを考慮して，蟻本を参考に実装したコードが以下である。

N = int(input())
XL = []
for _ in range(N):
    x,l = map(int,input().split())
    #腕の右端が左にあるものから調べる
    XL.append([x+l,x-l])
XL.sort()

ans, t = 0, -1e9
for i in range(N):
    if t <= XL[i][1]:
        ans += 1
        t = XL[i][0]
print(ans)