区間スケジューリング問題を考える
区間スケジュール問題では、後ろの値でソートして、前側から順に決定していくが、その答えが本当に最適解なのか考えてみた。
上段の図を、アルゴリズムから決定したものとして、それが最適解でなかったと仮定する。
その場合、両端のバーの中に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)