区間スケジューリング問題を考える

区間スケジュール問題では、後ろの値でソートして、前側から順に決定していくが、その答えが本当に最適解なのか考えてみた。

f:id:poohandduffy:20200811030335p:plain

上段の図を、アルゴリズムから決定したものとして、それが最適解でなかったと仮定する。

その場合、両端のバーの中に2個のバーが含まれる可能性が考えられるが、そのようなバーが存在するとすると、バーの決定順序は後ろの値でソートされているので、一個目のバーはBの様なバー(後ろの値が、Aの後ろの値よりも後ろ)が想定される。その上で、もう一個バーが存在するとなると、右端のバーの左端と、Bの右端の間に含まれる事になる(Cのバー)が、Cのバーが存在していた場合、区間スケジューリングのアルゴリズムでAと右端のバーの間に挿入されているはずで、矛盾する。

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

n = int(input())
ls = [(0, 0)] * n
for i in range(n):
    x, ln = map(int, input().split())
    l = x - ln
    r = x + ln
    ls[i] = (l, r)
#print(ls)

ls.sort(key=lambda x: x[1])
#print(ls)
last = -float('inf')
count = 0
for i in ls:
    if last <= i[0]:
        count += 1
        last = i[1]
print(count)