Problem:


Score : 200 points

Problem Statement

In a factory, there are N robots placed on a number line.
Robot i is placed at coordinate X_i and can extend its arms of length L_i in both directions, positive and negative.

We want to remove zero or more robots so that the movable ranges of arms of no two remaining robots intersect.
Here, for each i (1 \leq i \leq N), the movable range of arms of Robot i is the part of the number line between the coordinates X_i - L_i and X_i + L_i, excluding the endpoints.

Find the maximum number of robots that we can keep.

Constraints

1 \leq N \leq 100,000

0 \leq X_i \leq 10^9 (1 \leq i \leq N)

1 \leq L_i \leq 10^9 (1 \leq i \leq N)

If i \neq j, X_i \neq X_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 L_1
X_2 L_2
\vdots
X_N L_N

Output

Print the maximum number of robots that we can keep.

Sample Input 1

4
2 4
4 3
9 3
100 5

Sample Output 1

3

By removing Robot 2, we can keep the other three robots.

Sample Input 2

2
8 20
1 10

Sample Output 2

1

Sample Input 3

5
10 1
2 1
4 1
6 1
8 1

Sample Output 3

5



Sample input:
4
2 4
4 3
9 3
100 5


Sample output:
3

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,  input().split())) for i in range(N)]
A.sort(key=lambda x: x[0]+x[1])
now = -1e10
ans = 0
for i in range(N):
    [X, L] = A[i]
    if X-L >= now:
        now = X+L
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    robots = []
    for i in range(N):
        x, l = map(int, input().split())
        robots.append((x-l, x+l))
    robots = sorted(robots, key=lambda x: x[1])
    
    pre = -int(1e10)
    ans = 0
    for s, e in robots:
        if s >= pre:
            ans += 1
            pre = e
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
k_list = []

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

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

ptr = - 10 ** 10
cnt = 0

for item in k_list:
    if item[0] >= ptr:
        ptr = item[1]
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
lrl = []

for _ in range(n):
    x,l = map(int,input().split())
    lrl.append((x-l, x+l))


lrl = sorted(lrl, key=lambda x:x[1])
ans = 0
now = -float("inf")

for l,r in lrl:
    if now <= l:
        ans += 1
        now = r

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d = [[0, 0] for _ in range(n)]
for i in range(n):
    d[i] = list(map(int, input().split()))
d = [[dd[0], dd[1], dd[0]+dd[1]] for dd in d]
d.sort(key=lambda x: x[2])
ans = 0
target = d[0][2]
for dd in d:
    if dd[0] - dd[1] < target:
        ans += 1
    else:
        target = dd[2]
print(n-ans+1)

Submission status: Accepted

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
X_L = []
X_L_append = X_L.append
for _ in range(n):
    x, l = map(int, input().split())
    X_L_append((x+l, x-l))
X_L.sort()

ans = n
tmp = X_L[0][0]
for upper, lower in X_L[1:]:
  if lower < tmp:
    ans -= 1
  else:
    tmp = upper

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
XL=sorted([list(map(int,input().split())) for i in range(N)],key=lambda c:(c[0]+c[1]))
a=-float("inf")
ans=0
x,l=XL[0]
for i in range(N):
    X,L=XL[i]
    if X-L>=a:
        ans+=1
        a=X+L
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = []
for i in range(N):
    a, b = map(int, input().split())
    S.append((a-b, a+b))

S = sorted(S, key=lambda x: x[1])
res = 0
cur = -1e9
for i in range(N):
    if cur <= S[i][0]:
        res += 1
        cur = S[i][1]

print(res)

Submission status: Accepted

Solution code:
N = int(input())
M = [list(map(int, input().split())) for i in range(N)]
Q = [[m[0]-m[1], m[0]+m[1]] for m in M]
Q = list(sorted(Q, key=lambda x: x[1]))
NUM = 0
END = -10**9
for q in Q:
  if q[0] >= END:
    NUM += 1
    END = q[1]
print(NUM)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import defaultdict
from bisect import *
mod = 10**9+7

N = int(input())
XL = [list(map(int, input().split())) for i in range(N)]
A = [(X+L, X-L) for X, L in XL]
A.sort()
cnt, last = 0, A[0][0]
for s, t in A[1:]:
    if t < last:
        cnt += 1
    else:
        last = s
print(N-cnt)

Submission status: Accepted

Solution code:
n = int(input())
XL = [[int(x) for x in input().split()] for _ in range(n)]
XL.sort(key=lambda xl: xl[0] + xl[1])
count = 0
while len(XL) > 0:
    count += 1
    limit = XL[0][0] + XL[0][1]
    while len(XL) > 0 and XL[0][0] - XL[0][1] < limit:
        XL.pop(0)
print(count)

Submission status: Accepted

Solution code:
dleft = {}
dright = {}
count = 0
pre_right = None
n = int(input())

for i in range(n):
  x,l = list(map(int,input().split()))
  dleft[i+1] = x - l
  dright[i+1] = x + l

#print(dright)
sort_dright = sorted(dright.items(), key=lambda x:x[1])
#print(sort_dright)
for i in sort_dright:
  #print(pre_right)
  #print(dleft[i[0]])
  if pre_right is not None:
    if pre_right <= dleft[i[0]]:
      count += 1
      pre_right = dright[i[0]]
  else:
    count += 1
    pre_right = dright[i[0]]
print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
B = sorted([(A[i][0]-A[i][1],A[i][0]+A[i][1]) for i in range(N)],key=lambda x:x[0],reverse=True)
B = sorted(B,key=lambda x:x[1])
cnt = 1
cur = B[0][1]
for i in range(1,N):
    if B[i][0]>=cur:
        cnt += 1
        cur = B[i][1]
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
st = []
for i in range(N):
  x,l=map(int,input().split())
  s = max(x-l,0)
  t = min(x+l,10**9)
  st.append([t,s])
st.sort()

count = 0
lastT=0
for i in range(N):
  if st[i][1]>=lastT:
    count+=1
    lastT = st[i][0]
    
print(count)

Submission status: Accepted

Solution code:
n = int(input())
spans = []

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

ans = 0
cur_end_time = -float("inf")

for st, en in spans:
    if cur_end_time > st:
        continue
    ans += 1
    cur_end_time = en
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int,input().split())) for _ in range(n)]
#print(xl)
st = [[x-l, x+l] for x, l in xl] #得られた配列を自分の好きな値のリストに変換
#print(st)
st = sorted(st, key=lambda x: x[1]) #最大値の大きさkeyにすることで重なった箱型の時も防げる
#print(st)
result = 1
#最初は１
p = st[0][1] #keyを比較基準にした
for i in range(1, n):
    if p <= st[i][0]:
        p = st[i][1] #ループの基準を操作する
        result += 1 #カウントもする
print(result)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
import sys
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
XL=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0])

lst=[0]
for i in range(1,N):

    X1,L1=XL[lst[-1]]
    X2,L2=XL[i]
    #print(X1,L1,"1")
    #print(X2,L2,"2")
    if X1+L1<=X2-L2:
        lst.append(i)
        #print(i,"1")
    else:
        if X1+L1>X2+L2:
            lst.pop()
            lst.append(i)
            #print(i,"2")

print(len(lst))

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int,input().split())) for _ in range(n)]
st = [[x-l, x+l] for x, l in xl]
st = sorted(st, key=lambda x: x[1])
result = 1
p = st[0][1]
for i in range(1, n):
    if p <= st[i][0]:
        p = st[i][1]
        result += 1
print(result)

Submission status: Accepted

Solution code:
from operator import itemgetter

N=int(input())
XL=[list(map(int,input().split())) for _ in range(N)]

for xl in XL:
    xl.append(xl[0]+xl[1])

XL.sort(key=itemgetter(2))
#print(XL)
count=0
j=0

for i in range(1,N):
    if XL[j][2]>XL[i][0]-XL[i][1]:
        count+=1
    else:
        j=i

print(N-count)

Submission status: Accepted

Solution code:
N = int(input())
xl = [list(map(int, input().split())) for _ in range(N)]

from operator import itemgetter
st = sorted([[x - l, x + l] for x, l in xl], key=itemgetter(1))

#from operator import itemgetter
#xl = sorted(xl, key=itemgetter(1))
last = -float('Inf')
ans = 0
for s, t in st:
    #print(x, l)
    if s >= last:
        ans += 1
        last = t
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ts=[]
for i in range(N):
  x, l = map(int,input().split())
  s = max(x-l,0)
  t = min(10**9,x+l)
  ts.append([t,s])
ts.sort()

count = 0
lastT = 0
for i in ts:
  if i[1]>=lastT:
    count+=1
    lastT=i[0]
print(count)

Submission status: Accepted

Solution code:
N = int(input())
R = []
for _ in range(N):
    x, l = map(int, input().split())
    R.append([x-l, x+l])

R = sorted(R, key=lambda x: x[1])

ans = 0
tmp = -float('inf')
for l, r in R:
    if tmp <= l:
        ans += 1
        tmp = r
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    rng = []
    for i in range(N):
        X, L = map(int, input().split())
        first = X - L
        last = X + L
        rng.append((first,last))
    
    rng.sort(key=lambda x:x[1])

    prev_last = -float('inf')
    cnt = 0
    for i in range(N):
        if rng[i][0] >= prev_last:
            cnt += 1
            prev_last = rng[i][1]
    
    print(cnt)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
robots = [list(map(int, input().split())) for i in range(N)]

robots.sort()
robots_arms = [[r[0] - r[1],r[0], r[0] + r[1]] for r in robots ]#leftarm, x, right arm
left_robot = [-float('inf')]*3
ans = 0
for robot in robots_arms:
    if left_robot[2] <= robot[0]:
        ans += 1
        left_robot = robot
    elif left_robot[2] > robot[2]:
            left_robot = robot
    else:
        left_robot = left_robot
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = []
for i in range(N):
    xi, li = map(int, input().split())
    S.append([xi - li, xi + li])

from operator import itemgetter
S = sorted(S, key=itemgetter(1))

ans = 0
last = -1*float('Inf')
for si in S:
    if si[0] >= last:
        ans += 1
        last = si[1]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = []
for _ in range(n):
    x, l = map(int, input().split())
    s.append([x + l, x - l])
s.sort()
t = s[0][0]
ans = 1
for i in range(1, n):
    if s[i][1] >= t:
        ans += 1
        t = s[i][0]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

x_l_pairs = []
for _ in range(N):
    x, l = map(int, input().split(' '))
    x_l_pairs.append([x-l, x+l])

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

ret = 1
cur = x_l_pairs[0][1]
for left, right in x_l_pairs:
    # print(left, right)
    if cur <= left:
        ret += 1
        cur = right

print(ret)

Submission status: Accepted

Solution code:
N = int(input())
X = []
L = []
for i in range(N) :
    p, q = map(int,input().split())
    X.append(p)
    L.append(q)

Arm = []
for i in range(N) :
    Arm.append([X[i]-L[i], X[i]+L[i]])

Arm.sort(key=lambda x:x[1])
ans = 0
mxa = -10**10
for a in Arm :
    if a[0] >= mxa :
        mxa = a[1]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
robotList=[]
for i in range(n):
  x,l = map(int,input().split())
  s = max(x-l,0)
  t = min(10**9,x+l)  
  robotList.append([t,s])
  
robotList.sort()

count = 0
tmp = 0
for robot in robotList:
  if robot[1] >= tmp:
    count += 1
    tmp = robot[0]

print(count)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline())
xl = [list(map(int, stdin.readline().split())) for _ in range(N)]

inf = 10 ** 20

left = inf
right = -inf
ans = N

lr = []

for x, l in xl:
    lr.append([x - l, x + l])

lr.sort()

for l, r in lr:

    if l >= right:
        right = r
        left = l
    else:
        ans -= 1
        if r < right:
            right = r
            left = l

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
x_l = [0]*n
x_plus_l = [0]*n
# 左端から貪欲に埋めることができる
# 証明：f(x)をx以降に最大で残せる数とすると、現時点の可動域の右端をXとして　Xi<Xj の時、f(xi) >= f(xj)がそれまでの選び方によらず成り立つから
# つまり、X< xi-liとなるiの中でxi+liがminを選べば良い
# xi+Liでソートして毎回2分探索するとO(nlogn)で終わる => xi-liはソートされてないので2分探索できない
# xi-liでソートして、X以上の要素に対して、順番に X = max(X,xi+li)として更新し、
# X > Xi-Li になったらcnt += 1 し、その時点でXは確定する、と言うように尺取的なことをすると、
# ロボットを通過するのは各ロボットに対し、一度しかないのでO(n)でいける
# 変数：X,cnt
for i in range(n):
    x,l = map(int,input().split())
    x_l[i] = x-l
    x_plus_l[i] = x+l
x_l,x_plus_l = zip(*sorted(zip(x_l,x_plus_l)))
cnt = 1# 初期点は左端
i = 1#0から順番に見て行く
X = min(x_plus_l)#初期化 はx+l のmin
#print(X,x_l,x_plus_l)
#最初だけ 右端がminになる点をとるので x_l[i] >= Xになるように初期の調整をする
while i < n:# nになったら全点を探索しているので終了
    if x_l[i] >= X:
        cnt += 1
        X = x_plus_l[i]
        #print(i,cnt)
    else:
        if cnt != 1:
            X = min(X,x_plus_l[i])
    i += 1
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
input=stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:sum(x))
pre=-10**8
cnt=0
for i,j in l:
  if pre<=i-j:cnt+=1;pre=i+j
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
lst = []
for i in range(N):
    a, b = map(int, input().split())
    lst.append([a+b, a-b])
lst.sort()

cnt = 1
x = lst[0][0]
for i in lst:
    if x <= i[1]:
        cnt += 1
        x = i[0]

print(cnt)

Submission status: Accepted

Solution code:
num = int(input())
base = []
count = 0
t = -10**9

for i in range(num):
  temp = list(map(int,input().split()))
  base.append([temp[0]-temp[1],temp[0]+temp[1]])
  
base.sort(key=lambda x:x[1])

for temp in base:
  if t <= temp[0]:
    count = count + 1
    t = temp[1]
    
print(count)

Submission status: Accepted

Solution code:
N = int(input())
Range = []
for _ in range(N):
    X,L = map(int,input().split())
    Range.append([X-L,X+L])
counter = N
Range = sorted(Range,key=lambda x : x[1])
for i in range(1,N):
    if  Range[i - 1][1] > Range[i][0] :
        Range[i][1] = Range[i-1][1]
        counter -=1
print(counter)

Submission status: Accepted

Solution code:
N = int(input())
intervals = []
for _ in range(N):
  x, l = map(int, input().split())
  intervals.append((x-l,x+l))

intervals.sort(key=lambda ab: ab[1])
ans = 1
position = intervals[0][1]
for i in range(1,N):
  if position <= intervals[i][0]:
    ans += 1
    position = intervals[i][1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
Y = [list(map(int,input().split())) for _ in range(n)]
X = []
for y in Y:
    X.append([y[0]+y[1],y[0]-y[1]])
X.sort()
ans = n
right = X[0][0]
for i in range(1,n):
    left = X[i][1]
    if left < right:
        ans -= 1
    else:
        right = X[i][0]
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    robot = list()
    for i in range(n):
        x, l = map(int, input().split())
        robot.append([x - l, x + l])

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

    ans = 0
    arm_pos = -10 ** 9 - 1
    for r in robot:
        if r[0] >= arm_pos:
            ans += 1
            arm_pos = r[1]

    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
st = []
for i in range(n):
    x,l = map(int,input().split())
    st.append([x-l,x+l])

st.sort(key=lambda x:x[1])
t0 = st[0][1]
cnt = n
for s,t in st[1:]:
    if t0 <= s:#もし終わりが次の始まりより早かったら
        t0 = t
    else:
        cnt -=1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
st = []
for i in range(n):
    x, l = map(int, input().split())
    st.append([x + l, x - l])

st.sort()
cnt = 1
right = st[0][0]
for i in range(1, n):
    if right <= st[i][1]:
        right = st[i][0]
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
l_rng = []
for i in range(n):
  x,l = map(int,input().split() )
  l_rng.append([x-l,x+l])
l_rng.sort(key=lambda x: x[1] )

#右端の値を初期化
migigawa = l_rng[0][1]
cnt = 1
for i in l_rng:
  if migigawa <= i[0]:
    migigawa = i[1]
    cnt = cnt +1
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
x=[]
for i in range(n):
    a,b=l[i][0],l[i][1]
    x.append([a-b,a+b])
x.sort(key=lambda x:x[1])
now=x[0][1]
ans=1
for i in range(1,n):
    if x[i][0]>=now:
        ans+=1
        now=x[i][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    robot = int(input())
    right_lim = 0
    answer = 1
    robot_info = []
    for _ in range(robot):
        coordinate, arm_length = map(int, input().split())
        robot_info.append([coordinate - arm_length, coordinate + arm_length])
    robot_info = sorted(robot_info, key=lambda x: x[1])
    for i in range(robot):
        if i == 0:
            right_lim = robot_info[i][1]
        elif right_lim <= robot_info[i][0]:
            right_lim = robot_info[i][1]
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
X = []
L = []

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

robo = sorted([(X[i]-L[i], X[i]+L[i]) for i in range(n)], key=itemgetter(1))

ans = 0
end = -float("inf")
for i in range(n):
    if end <= robo[i][0]:
        ans += 1
        end = robo[i][1]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]

rXL = []
for i, j in XL:
    rXL.append([i - j, i + j])
rXL = sorted(rXL, key = lambda x: x[1])
TF = [True for _ in range(N)]

maxr = rXL[0][1]
for i in range(1, N):
    if maxr <= rXL[i][0]:
        maxr = rXL[i][1]
    else:
        TF[i] = False

print(sum(TF))

Submission status: Accepted

Solution code:
n = int(input())

a = []
for _ in range(n):
    X, L = map(int, input().split())
    a.append([X + L, X - L])

a.sort()

ans = 0
b = - float('inf')
for t, s in a:
    if s >= b:
        b = t
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  n = int(input())
  #XL = [[int(i) for i in input().split()] for _ in range(n)]
  L = []
  for i in range(n):
    x, l = map(int, input().split())
    L.append((x-l, x+l))
  L = sorted(L, key = itemgetter(1))
  r_max = -10 ** 18
  ans=0
  for i in range(n):
    l_end, r_end = L[i]
    if r_max <= l_end:
      ans+=1
      r_max = r_end
  print(ans)
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from operator import itemgetter

def solve():
    N = int(input())
    X = []
    for i in range(N):
        xx, ll = map(int, input().split())
        X.append((xx-ll, xx+ll))
    X.sort(key=itemgetter(1))
    count = 0
    cur = -float('inf')
    for i in range(N):
        c, d = X[i]
        if cur <= c:
            count += 1
            cur = d
    return count

print(solve())

Submission status: Accepted

Solution code:
n = int(input())

l = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    l.append([tmp[0] - tmp[1],tmp[0] + tmp[1]])

l.sort()
l = l[::-1]
now = l[0][0]
ans = 1
for i in range(1,n):
    if now >= l[i][1]:
        now = l[i][0]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
  x,y=map(int,input().split())
  l.append([x-y,x+y])
count=0
l=sorted(l)
l=l[::-1]
count+=1
now=l[0][0]
for i in range(1,n):
  if now>=l[i][1]:
    now=l[i][0]
    count+=1
  else:
    pass
print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    x,l=map(int,input().split())
    a.append([x-l,x+l])
a=sorted(a,key=lambda x: x[1])
ans=n
t=a[0][1]
for i in range(1,n):
    if a[i][0]<t:
        ans-=1
    else:
        t=a[i][1]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
  x,l=map(int,input().split())
  a.append([x+l,max(0,x-l)])
a.sort()
r=0
c=0
for i in range(n):
  if a[i][1]>=r:
    r=a[i][0]
    c+=1
print(c)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
lis = []
ans = []
lis_append=lis.append
for i in range(N):
    x,l = map(int, input().split(" "))
    lis_append((x+l,x-l))
lis.sort()
lis = deque(lis)
ans.append(lis.popleft())
while lis:
    a = lis.popleft()
    if a[1] >= ans[-1][0]:
        ans.append(a)
print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
lis = []
for i in range(n):
    x, l = map(int, input().split())
    lis.append([x-l,x+l])
lis = sorted(lis, key=lambda x:x[1])
cnt = 1
p = lis[0][1]
for i in range(1, n):
    if lis[i][0] >= p:
        p = lis[i][1]
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
rob = []
for i in range(N):
  x, l = map(int, input().split())
  rob.append((x-l, x+l))
rob.sort(key=lambda x: x[1])
t = rob[0][0]
ans = 0
for l, r in rob:
  if t <= l:
    ans += 1
    t = r
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arms=[]
for _ in range(n):
    x,l=map(int,input().split())
    arms.append([x-l,x+l])
arms.sort()
now=arms[0][1]
cnt=0
for arm in arms[1:]:
    if now<=arm[0]:
        now=arm[1]
    elif now<=arm[1]:
        cnt+=1
    else:
        cnt+=1
        now=arm[1]
print(n-cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())

robots = [tuple(map(int, input().split())) for _ in range(n)]
robots = sorted([(x-t, x+t) for x, t in robots], key=itemgetter(1))

counter = 1
now = robots[0][1]
for robot in robots[1:]:
    if now <= robot[0]:
        counter += 1
        now = robot[1]

print(counter)

Submission status: Accepted

Solution code:
N = int(input())
arms = []

for _ in range(N):
    X, L = map(int, input().split())
    tmp = (X-L, X+L)
    arms.append(tmp)

arms.sort()

trash_count = 0
focus_point = 0

focus_point = arms[0][1]
for arm in arms[1:]:
    if focus_point <= arm[0]:
        focus_point = arm[1]
    elif focus_point <= arm[1]:
        trash_count += 1
    else:
        trash_count += 1
        focus_point = arm[1]

print(N-trash_count)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
X = [0]*N
L = [0]*N
lis = deque()
for i in range(N):
    X[i], L[i] = map(int, input().split())
    lis.append([i,X[i]-L[i], X[i]+L[i]])

lis = sorted(lis, key=lambda x:x[2])
lis = deque(lis)

end = lis[0][2]
start = lis[0][1]
lis.popleft()
cnt = 1
while lis:
    x, y, z = lis.popleft()
    if y < end:
        continue
    elif y >= end:
        start = y
        end = z
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
L=[list(map(int,input().split())) for i in range(N)]
R=[]
for i in range(N):
  a=max(0,L[i][0]-L[i][1])
  b=L[i][0]+L[i][1]
  R.append([b,a])
R.sort()

ans=0
last=0
for i in range(N):
  if last<=R[i][1]:
    ans+=1
    last=R[i][0]
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    robot = [None]*n
    for i in range(n):
        x, arm = map(int, input().split())
        robot[i] = [x - arm, x + arm]
    robot.sort(key=lambda x: x[1])
    ans = 0
    x = -1 * (10)**9
    for i in range(n):
        if x <= robot[i][0]:
            ans += 1
            x = robot[i][1]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]

R=[]
for i in range(N):
    a=max(0,XL[i][0]-XL[i][1])
    b=XL[i][1]+XL[i][0]
    R.append([b,a])
R.sort()

ans=0
con_l=0
for i in range(N):
    if con_l <= R[i][1]:
        ans += 1
        con_l = R[i][0]
print(ans)

'''
①入力
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]
Nはロボットの個数
XLは座標Xと腕の長さLのリスト

②リストの編集
ロボットの腕の始点(a)と終点(b)を保存するリスト(R)を作成する

R=[]
for i in range(N):
    a=max(0,XL[i][0]-XL[i][1])
    b=XL[i][1]+XL[i][0]
    R.append([b,a])
R.sort()
リストRは終点昇順でソートしておく

③区間スケジューリング＆出力
ans=0
con_l=0
for i in range(N):
    if con_l <= R[i][1]:
        ans += 1
        con_l = R[i][0]
print(ans)
ansは選んだロボットの個数
con_lは最後に選んだロボットの腕の終点

forループ内の処理は最後に選んだロボットの終点(con_l)より大きい始点(R[i][1])を持つロボットを貪欲的に探索するようになっている
Rは終点昇順でソートしてあるため、探索していく中で最小の終点のものを常に選択するようになっている
見つかるたびにansに+1してcon_lを更新する
出力して終了
'''

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
data = []
for i in range(N):
    X,L = [int(x) for x in stdin.readline().rstrip().split()]
    data.append((X+L,X-L))

ans = 0
left = -10**9-1
for k,j in sorted(data):
    if j >= left:
        left = k
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

P = [0] * 150

robot = []

for i in range(N):
    X, L = map(int,input().split())

    left = X-L
    right = X+L

    # 右端でソートしたいため右端を配列1にする
    robot.append([right,left])

robot = sorted(robot)

cnt = 0 #ロボット数
last_right = -float('inf') #最後の右端

for i in range(N):
    if last_right <= robot[i][1]:
        cnt += 1
        last_right =  robot[i][0]

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
ran = [[xl[i][0]-xl[i][1], xl[i][0]+xl[i][1]] for i in range(n)]
ran = sorted(ran, key=lambda x:x[1])
ans = n
right = ran[0][1]
for i in range(1, n):
  l, r = ran[i]
  if l < right:
    ans -= 1 
  else:
    right = r 
 
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
ran = [[xl[i][0]-xl[i][1], xl[i][0]+xl[i][1]] for i in range(n)]
ran = sorted(ran, key=lambda x:x[1])
ans = 1
right = ran[0][1]
for i in range(n):
  l, r = ran[i]
  if l >= right:
    ans += 1 
    right = r 

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
data=[]
for i in range(n):
    x,l=map(int,input().split())
    data.append([x+l,x-l])
data.sort()
ans=1
arm=data[0][0]
for i in range(n):
    if arm<=data[i][1]:
        ans+=1
        arm=data[i][0]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
robot = []
for i in range(n):
    x, l = map(int,input().split())
    robot.append([x + l, x - l]) #left, right
robot.sort()
preright = robot[0][1]
ans = 0
for i in range(n):
    left = robot[i][1]
    #print(preright, left)
    if preright <= left:
        ans += 1
        preright = robot[i][0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = [list(map(int,input().split())) for _ in range(N)]

ans = N
for i in l:
    x = 0 if i[0]-i[1] < 0 else i[0]-i[1]
    i[1] = i[0]+i[1]
    i[0] = x
    
l.sort(key=lambda x:x[1])

right = 0
for i in range(N):
    if right > l[i][0]:
        ans-=1
    else:
        right = l[i][1]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = []

for _ in range(N):
    X, L = map(int, input().split())
    l.append((X-L, X+L))

l.sort(key=lambda x:x[1])
before = -10**9
ans = 0

for i, j in l:
    if i>=before:
        ans += 1
        before = j

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
b = []
for i in range(n):
	x, l = map(int, input().split())
	b.append([x+l,x-l])
b.sort()

r = -10**10
ans = 0
for i in b:
	if i[1] >= r:
		ans += 1
		r = i[0]
	else:
		continue
print (ans)

Submission status: Accepted

Solution code:
N = int(input())

#改行入力 X,Y
L = [[0,0,0,0] for i in range(N)]
t=-1*(10**9)
s=0
for i in range(N):
    L[i][0],L[i][1] = map(int,input().split())
    L[i][2]=L[i][0]+L[i][1]
    L[i][3]=L[i][0]-L[i][1]

L=sorted(L,key=lambda x: x[2])

for i in range(N):
    if(t<=L[i][3]):
        s+=1
        t=L[i][2]

print(s)

Submission status: Accepted

Solution code:
N = int(input())
X = [0]*N
L = [0]*N
Y = []

for i in range(N):
    X, L = map(int, input().split())
    Y.append([X+L, X-L])

Y.sort()

count = 0
length = -10**10
for i in range(N):
    if Y[i][1] >= length:
        count += 1
        length = Y[i][0]

print(count)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N, *xl = map(int, read().split())
    XL = []

    for x, l in zip(*[iter(xl)]*2):
        XL.append((x-l, x+l))

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

    ans = 0
    end = -10**9
    for s,e in XL:
        if s >= end:
            ans += 1
            end = e
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
X=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append([a+b,a-b])
X.sort()
D={}
D[0]=1
exe=[0]
for i in range(1,N):
    k=X[i][0]
    if X[i][1]<X[exe[-1]][0]:
        D[i]=D[exe[-1]]
    else:
        D[i]=D[exe[-1]]+1
        exe.append(i)
print(len(exe))

Submission status: Accepted

Solution code:
N = int(input())
a = []
for i in range(N):
	X, L = map(int, input().split())
	a.append((X + L, X - L))
a.sort()
b = [a[0][0]]
i = 1
while i < N:
	if b[len(b) - 1] <= a[i][1]:
		b.append(a[i][0])
	i += 1
print(len(b))

Submission status: Accepted

Solution code:
INF = float("inf") #const

def main():
    n = int(input())
    ls = [list(map(int,input().split())) for _ in range(n)]
    #start ls[i][0] - ls[i][1]. goal ls[i][0] + ls[i][1]
    robot = [(ls[i][0] + ls[i][1],ls[i][0] - ls[i][1]) for i in range(n)]
    robot = sorted(robot,key = lambda x: x[0])
    #(goal,start)

    ans = 0; latest = -INF
    for i in range(n):
        if latest <= robot[i][1]:
            ans += 1
            latest = robot[i][0]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
xllist=[list(map(int,input().split())) for _ in range(n)]
s_e=[]
for xl in xllist:
    s_e.append([xl[0]-xl[1],xl[0]+xl[1]])
s_e.sort(key=lambda x: x[1])
now=s_e.pop(0)[1]
ans=1
for xl in s_e:
    if now<=xl[0]:
        ans+=1
        now=xl[1]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
ans=1
r=arr[0][0]+arr[0][1]
for i in range(1,n):
  l=arr[i][0]-arr[i][1]
  if r<=l:
    ans+=1
    r=arr[i][0]+arr[i][1]
  else:
    r=min(r,arr[i][0]+arr[i][1])
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

n=int(input())
s = [list(map(int, input().split())) for i in range(n)]

x=[]
for i in range(n):
    x.append((s[i][0]-s[i][1],s[i][0]+s[i][1]))

x=sorted(x,key=itemgetter(1))
ans=1
r=x[0][1]
for i in range(1,n):
    if r<=x[i][0]:
        ans+=1
        r=x[i][1]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robot_list = []
for i in range(N):
  X, L = map(int, input().split())
  left_edge = X - L
  right_edge = X + L
  robot_list.append([left_edge, right_edge])

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

res = 0
index = - pow(10, 10)
for i in range(N):
  if robot_list[i][0] >= index:
    index = robot_list[i][1]
    res += 1

print(res)

Submission status: Accepted

Solution code:
n=int(input())
xl=[]

for i in range(n):
    x,l=list(map(int,input().split()))
    xl.append([x-l,x+l,x])

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

armmax=-10**10
cnt=0
for left,right,x in xl:
    if armmax<=left:
        armmax=right
        cnt+=1

print(cnt)