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())
ts = []
for i in range(n):
    x, l = map(int, input().split())
    t = x + l
    s = x - l
    ts.append([t, s])

ts.sort()
ans = 0
T = float("inf") * - 1
for i in range(n):
    if T <= ts[i][1]:
        ans += 1
        T = ts[i][0]

print(ans)

Submission status: Accepted

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

cur=-10**9
ans=0
for xx in x:
    if xx[1]>=cur:
        ans+=1
        cur=xx[0]
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())
R = [0]*N
for i in range(N):
    X_i, L_i = map(int, input().split())
    R[i] = (X_i-L_i,X_i+L_i)
R.sort(key=itemgetter(1))

ans, loc = 0, -(float('inf'))
for i in range(len(R)):
    if loc <= R[i][0]:
        ans += 1
        loc = R[i][1]
print(ans)

Submission status: Accepted

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

for i in range(N):
    X, L = map(int, input().split())
    X1.append([X+L, X-L])
X1.sort()
ans = -10**10
cnt = 0
for j in range(N):
    if(X1[j][1] >= ans):
        cnt += 1
        ans = X1[j][0]
print(cnt)

Submission status: Accepted

Solution code:
import sys
N = int(input())
a = sorted([(x+l, x-l) for x, l in (map(int, l.split()) for l in sys.stdin)])

last = a[0][0]
ans = 1

for r, l in a[1:]:
    if(last <= l):
        ans += 1
        last = r
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
a = sorted([(x + l, x - l) for x, l in (map(int, l.split()) for l in sys.stdin)])

last = a[0][0]
ans = 1

for r, l in a[1:]:
    if last <= l:
        ans += 1
        last = r

print(ans)

Submission status: Accepted

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

newXL = sorted([[x-l, x+l] for x, l in XL], key=lambda x:x[1])

previous = 0
total = 1

for i in range(1, N):
  if newXL[i][0] < newXL[previous][1]:
    pass
  else:
    previous = i
    total += 1
    
print(total)

Submission status: Accepted

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

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

L.sort(key=lambda x:x[1])
ans=0
cur=-11111111111111111
for a,b in L:
  if a>=cur:
    cur=b
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

s_p, e_p = [0] * N, [0] * N
for i in range(N):
    X, L = map(int, input().split())
    s_p[i] = X - L
    e_p[i] = X + L

# sort by end point
c = sorted(zip(e_p, s_p))
e_p, s_p = zip(*c)

# greedy
e = -float('inf')
count = 0
for i in range(N):
    if s_p[i] >= e:
        count += 1
        e = e_p[i]
print(count)

Submission status: Accepted

Solution code:
n = int(input())

xl = []

for i in range(n):
    x,l = map(int,input().split())
    xl.append([x+l,x-l])
xl.sort()
ans = -10**10
count = 0
for j in range(n):
    if xl[j][1] >= ans:
        count +=1
        ans = xl[j][0]
print(count)

Submission status: Accepted

Solution code:
N = int(input())
R = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[0]+x[1])

remain = list(range(N))
ans = N
left = 0
i = 1
while i < N:
  x_l, length_l = R[left]
  x, length = R[i]
  if x-x_l < length_l+length:
    ans -= 1
  else:
    left = i
  i += 1
print(ans)

Submission status: Accepted

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

s = []
f = []
res = 1

for i in range(n):
    s.append(l[i][0]-l[i][1])
    f.append([l[i][0]+l[i][1], i])
    
f = sorted(f)
#print(f)

m = f[0][0]
for i in range(1, n):
    if s[f[i][1]] >= m:
        res += 1
        m = f[i][0]
    
print(res)

Submission status: Accepted

Solution code:
n = int(input())
l = []
for _ in range(n):
  x,y = map(int, input().split())
  l.append([x+y,x-y])
l=sorted(l)
 
tmp = l[0][0]
count = n
for p in l[1:]:
  if tmp <= p[1]:
    tmp = p[0]
  else:
    tmp = min(tmp,p[0])
    count -= 1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
lis = []
for _ in range(n):
  x, l= list(input().split(" "))
  p_d = int(x) + int(l)
  m_d = int(x) - int(l)
  lis.append([p_d, m_d])

lis.sort()
a = -10 ** 10
x = 0

for b in range(n):
  if lis[b][1] >= a:
    x += 1
    a = lis[b][0]

print(x)

Submission status: Accepted

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

mlist=[]
for i in range(N):
    mlist.append([TS[i][0] + TS[i][1], TS[i][0] - TS[i][1]])

mlist.sort()

cur = -10**10
ans=0
for i in range(N):
    if mlist[i][1] >= cur:
        ans+=1
        cur = mlist[i][0]
print(ans)

Submission status: Accepted

Solution code:
H = int(input())
x = [[float('inf')]*2 for i in range(H)]

for i in range(H):
    X, L = map(int, input().split())
    x[i][0] = X - L
    x[i][1] = X + L

from operator import itemgetter
sf = sorted(x, key=itemgetter(1))

ans = 0
last = float('inf')*-1

for i in range(H):
    if last <= sf[i][0]:
        ans += 1
        last = sf[i][1]

print(ans)

Submission status: Accepted

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

#始まりと終わりの時間の多次元リストに組み替える
st = [(xl[i][0]-xl[i][1],xl[i][0]+xl[i][1]) for i in range(n)]
#終わりの時間でソート！
st.sort(key=lambda x:x[1])

ans = 0
#最後に選んだ時間の仕事の終了時間
last = - 10**10

for i in range(n):
    if last <= st[i][0]:
        ans += 1
        last = st[i][1]

print(ans)

Submission status: Accepted

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

XL.sort(key = lambda x:sum(x))
ans = 0
f = -1000000001
for x,l in XL:
    if x - l >= f:
        ans += 1
        #print(f)
        f = x + l
print(ans)

Submission status: Accepted

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

XL.sort(key=lambda x: sum(x))
f = -99999999999
ans = 0
for x, l in XL:
    if x - l >= f:
        ans += 1
        f = x + l

print(ans)

Submission status: Accepted

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

d = []
for x, l in XL:
    d.append([x + l, l])

d.sort()

inf = float('inf')

pre = - inf
ans = N
for dd in d:
    if dd[0] - 2 * dd[1] < pre:
        ans -= 1
    else:
        pre = dd[0]

print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N = iin()
XL = [iln() for _ in range(N)]

XL = sorted(XL, key=lambda x: x[0]+x[1])

prev = -10**9
ans = 0
for i in range(0, N):
    if prev <= XL[i][0] - XL[i][1]:
        ans += 1
        prev = XL[i][0] + XL[i][1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
RL = [[0, 0] for _ in range(N)]
for i in range(N):
    left = XL[i][0] - XL[i][1]
    right = XL[i][0] + XL[i][1]
    RL[i][0] = left
    RL[i][1] = right
 
RL.sort(key=lambda x: x[1])
now_right = RL[0][1]
cnt = 0
for i in range(1, N):
    if now_right <= RL[i][0]:
        now_right = RL[i][1]
    else:
        cnt += 1
print(N - cnt)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
XL=[list(map(int,input().split())) for _ in range(n)]
XL.sort(key=lambda x:x[0]+x[1])
edge=XL[0][0]-XL[0][1]-1
ans=0
for x,l in XL:
    left=x-l
    right=x+l
    if left>=edge:
        ans+=1
        edge=right
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
RL = [[0, 0] for _ in range(N)]
for i in range(N):
    left = XL[i][0] - XL[i][1]
    right = XL[i][0] + XL[i][1]
    RL[i][0] = left
    RL[i][1] = right

RL.sort(key=lambda x: x[1])
now_right = RL[0][1]
cnt = 0
for i in range(1, N):
    if now_right <= RL[i][0]:
        now_right = RL[i][1]
    else:
        cnt += 1
print(N - cnt)

Submission status: Accepted

Solution code:
n = int(input())
LR = [None] * n
for i in range(n):
    x, l = map(int, input().split())
    LR[i] = (x - l, x + l)
LR.sort(key=lambda lr: lr[1])
count = 1
cur = LR[0][1]
for l, r in LR[1:]:
    if cur <= l:
        count += 1
        cur = r
print(count)

Submission status: Accepted

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

mlist=[]
for i in range(N):
    mlist.append([TS[i][0] + TS[i][1], TS[i][0] - TS[i][1]])

mlist.sort()

cur = -10**10
ans=0
for i in range(N):
    if mlist[i][1] >= cur:
        ans+=1
        cur = mlist[i][0]
print(ans)

Submission status: Accepted

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

mlist=[]
for i in range(N):
    mlist.append([TS[i][0] + TS[i][1], TS[i][0] - TS[i][1]])

mlist.sort()

cur = -10**10
ans = 0
for i in range(N):
    if mlist[i][1] >= cur:
        ans+=1
        cur = mlist[i][0]
print(ans)

Submission status: Accepted

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

mlist=[]
for i in range(N):
    mlist.append([TS[i][0] + TS[i][1], TS[i][0] - TS[i][1]])

mlist.sort()

cur = -10**10
ans = 0
for i in range(N):
    if mlist[i][1] >= cur:
        ans+=1
        cur = mlist[i][0]
print(ans)

Submission status: Accepted

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

cur = -10**10
ans = 0
for i in range(N):
    if TS[i][1] >= cur:
        ans+=1
        cur = TS[i][0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
TS = []
for i in range(N):
    X, L = map(int, input().split())
    TS.append((X + L, X - L))
TS = sorted(TS)
cur = -10**10
ans = 0
for i in range(N):
    if TS[i][1] >= cur:
        ans+=1
        cur = TS[i][0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
TS = []
for i in range(N):
    X, L = map(int, input().split())
    TS.append((X + L, X - L))
TS = sorted(TS)
cur = -10**10
ans = 0
for i in range(N):
    if cur <= TS[i][1]:
        ans += 1
        cur = TS[i][0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XL =[list(map(int, input().split())) for _ in range(N)]
LR = [[XL[i][0] - XL[i][1], XL[i][0] + XL[i][1]] for i in range(N)]
LR.sort(key = lambda x: x[1])

cp = LR[0][1]

ans = 0

for i in range(1,N):
	if LR[i][0] < cp:
		ans += 1
	else:
		cp = LR[i][1]
print(N-ans)

Submission status: Accepted

Solution code:
n = int(input())
li_a = []
for i in range(n):
  a = list(map(int, input().split()))
  li_a.append(a)
li = list(sorted(li_a))
ans = 0
b = li[0][0] + li[0][1]
for i in range(n-1):
  if li[i+1][0] - li[i+1][1] >= b:
    b = li[i+1][0] + li[i+1][1]
  else:
    b = min(b, li[i+1][0]+li[i+1][1])
    ans += 1
print(n-ans)

Submission status: Accepted

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

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

# startが被らないendが小さいもの

ans = 0
robot.sort(key=lambda x: x[1])
last = - float('inf')
for start, end in robot:
    if start >= last:
        ans += 1
        last = end

print(ans)

Submission status: Accepted

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

# startが被らないendが小さいもの

ans = 0
robot.sort(key=lambda x: x[1])
last = - float('inf')
for start, end in robot:
    if start >= last:
        ans += 1
        last = end

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,x+l])
a.sort(key=lambda x:x[1])
r=-10**10
ans=0
for i in range(n):
    if a[i][0]>=r:
        ans+=1
        r=a[i][1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ar = []
mi = 0
mx = 0
count = 1
for i in range(n):
    a,b = map(int,input().split(" "))
    br = [a+b,a-b]
    ar.append(br)
ar.sort()
for i,r in enumerate(ar):
    if i == 0:
        mx = r[0]
    else:
        if mx <= r[1]:
            count += 1
            mx = r[0]
print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter

def solve():
    N = int(input())
    C = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        C.append((a-b, a+b))

    C.sort(key = itemgetter(1))
    
    c = 0
    cur = -float('inf')
    for i in range(N):
        if cur <= C[i][0]:
            c += 1
            cur = C[i][1]

    return c

print(solve())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    P = [None] * N
    for i in range(N):
        X, L = map(int, input().split())
        l, r = X-L, X+L
        P[i] = (l, r)
    P.sort(key=lambda x: x[1])
    ans = 0
    lbound = -float("inf")
    for l, r in P:
        if l < lbound:
            continue
        ans += 1
        lbound = r
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = []
for _ in range(n):
    x, l = LI()
    L += [(x - l, x + l)]

L.sort(key=lambda x:x[1])
ret = -INF
cnt = 0
for i in range(n):
    left, right = L[i]
    if ret <= left:
        ret = right
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
L = []
for i in range(n):
  a,b = map(int,input().split())
  L.append([a+b,a-b])
L.sort()
ans = 0
right = -10**10
for i in range(n):
  if L[i][1] >= right:
    ans += 1
    right = max(right,L[i][0])
print(ans)

Submission status: Accepted

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

# アームが伸びる範囲に置き換える
a = []
for i in range(N):
    a.append([XL[i][0] - XL[i][1], XL[i][0] + XL[i][1]])
# アームが届く最大座標でソートする
a = sorted(a, key=lambda x: x[1])

ans = 0
cur = - float('inf')
for i in range(N):
    if a[i][0] >= cur:
        ans += 1
        cur = a[i][1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
robot = []
for _ in range(n):
    x, l = map(int, input().split())
    arm_left = x - l
    arm_right = x + l
    robot.append([arm_left, arm_right])

robot.sort(key=lambda x: x[1])
count = 0
current_right = -1000000000
for i in range(n):
    if robot[i][0] >= current_right:
        count += 1
        current_right = robot[i][1]

print(count)

Submission status: Accepted

Solution code:
N=int(input())


x=[list(map(int,input().split())) for i in range(N)]
width=[[x[i][0]-x[i][1],x[i][0]+x[i][1]] for i in range(N)]

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

ans=0
thr=-10**9
for i in range(N):
    if thr<=width[i][0]:
        ans+=1
        thr=width[i][1]

print(ans)

Submission status: Accepted

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

distances = sorted([[x + l, x - l] for x, l in xl])

ans = 0
t = -float('inf')
for i in range(len(distances)):
    if t <= distances[i][1]:
        ans += 1
        t = distances[i][0]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

L = []
R = []

for i in range(N):
    x,l = map(int,input().split())
    L.append( x-l )
    R.append( x+l )

R,L = zip(*sorted(zip(R,L)))
cnt = 1
maxR = R[0]
for i in range(1,N):
    if maxR <= L[i]:
        cnt += 1
        maxR = R[i]
            
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

L = []
R = []

for i in range(N):
    x,l = map(int,input().split())
    L.append( x-l )
    R.append( x+l )

R,L = zip(*sorted(zip(R,L)))
cnt = 1
maxR = R[0]
for i in range(1,N):
    if maxR <= L[i]:
        cnt += 1
        if maxR < R[i]:
            maxR = R[i]
            
print(cnt)

Submission status: Accepted

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

for i in range(n):
    xi,li = map(int, input().split( ))
    R.append((xi+li,xi-li,i))
#左から貪欲
R.sort()
ans = 0
right = -10**10
for i in range(n):
    if R[i][1]>=right:
        ans+=1
        right = R[i][0]

print(ans)

Submission status: Accepted

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

robots.sort()

max_point = 0
count = 0

for i,elem in enumerate(robots):
    if i == 0:
        max_point = elem[0]+elem[1]
        prev_elem = elem
    else:
        if max_point <= elem[0]-elem[1]:
            max_point = elem[0] + elem[1]
            prev_elem = elem
        else:
            count += 1
            if max_point >= elem[0] + elem[1]:
                max_point = elem[0] + elem[1]
                prev_elem = elem

print(n-count)

Submission status: Accepted

Solution code:
def main():
    N = int(input())

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

    r = -10**10
    ans = 0
    for s in S:
        if s[0] >= r and s[1] >= r:
            r = s[1]
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
length = int(input())
target = []
for i in range(length):
    s, e = map(int, input().split(" "))
    target.append([s - e, s + e])
target.sort(key = lambda x: x[1])
answer = 0
before_e = -float("inf")
for s, e in target:
    # print(before_e, s, e)
    if s < before_e:
        answer += 1
    else:
        before_e = e
print(length - answer)

Submission status: Accepted

Solution code:
n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    x.append([i*3, 1])
l = []
y = 0
for i in range(n):
    l.append([x[i][0]+x[i][1], x[i][0]-x[i][1]])
l.sort()
z = l[0][1]
for i in range(n):
    if l[i][1] >= z:
        y += 1
        z = l[i][0]
print(y)

Submission status: Accepted

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

N = int(input())
robots, count = [], 0
for x in range(N):
    X, L = map(int, input().split())
    robots.append((X+L, X-L))
robots.sort()
node = -10**12
for end, start in robots:
    if start >= node:
        node = end
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n = int(input())
robots = []
for i in range(n):
    x, l = [int(item) for item in input().split()]
    robots.append((x+l, x-l))
 
robots.sort()
 
cnt = 0
node = -10**12
for end, start in robots:
    if start >= node:
        node = end
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
robots, count = [], 0
for x in range(N):
    X, L = map(int, input().split())
    robots.append((X+L, X-L))
robots.sort()
node = -10**12
for end, start in robots:
    if start >= node:
        node = end
        count += 1
print(count)

Submission status: Accepted

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

ans = 0
for i in range(n):
  if i == 0:
    temp = L[i][0]
    ans += 1
  else:
    if L[i][1] >= temp:
      ans += 1
      temp = L[i][0]
    else:
      continue
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
lin = [[i[0]-i[1],i[0]+i[1]] for i in li]
lin.sort(key=lambda x:(x[1]))
count = 0
now = -10**10
for i in lin:
    if i[0] >= now:
        now = i[1]
        count += 1
print(count)

Submission status: Accepted

Solution code:
# 解き直し https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b
N = int(input())
R = [None] * N
for i in range(N):
    X, L = map(int, input().split())
    R[i] = (X-L, X+L)
# 右端でソート
R.sort(key=lambda x: x[1])
ans = N
max_R = R[0][1]
for i in range(1, N):
    if R[i][0] < max_R:
        ans -= 1
    else:
        max_R = R[i][1]
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from operator import itemgetter

n = int(input())
s = []
p = []
for i in range(n):
    x, l = map(int, input().split())
    s.append(x - l)
    p.append(x + l)
c = zip(s, p)
c = sorted(c, key=itemgetter(1))
s, p = zip(*c)

arm = p[0]
ans = 1
for i in range(1, n):
    if arm <= s[i]:
        ans += 1
        arm = p[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R = [tuple(map(int, input().split())) for _ in range(N)]
# 左端でソート
R.sort(key=lambda x: x[0]-x[1])
prev_L_arm = R[0][0] - R[0][1]
prev_R_arm = R[0][0] + R[0][1]
ans = N
for i in range(1, N):
    L_arm = R[i][0] - R[i][1]
    R_arm = R[i][0] + R[i][1]
    if L_arm < prev_R_arm:
        prev_R_arm = min(prev_R_arm, R_arm)
        ans -= 1
    else:
        prev_R_arm = R_arm
print(ans)

Submission status: Accepted

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

N = int(input())
R = []

for i in range(N):
	x,l = map(int, input().split())
	R.append([max(x-l,0),x+l])
R.sort(key = lambda r : r[1])

ans = N
lr = -1
for i in range(N):
	if(lr > R[i][0]):
		ans -=1
		continue
	else:
		lr = R[i][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    for current in robots:
        if prev and prev[0] + prev[1] > current[0] - current[1]:
            total -= 1
        else:
            prev = current
            
    return total
 
N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = sorted(ROBOTS, key=lambda x: x[0] + x[1])
print(solve(ROBOTS))

Submission status: Accepted

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

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

right = -float('inf')

ans = 0
for x, l in XL:
    s, t = x-l, x+l
    if s >= right:
        right = t
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
sum=0
lis=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0]+x[1])
min=-10**18
for x in lis:
    if min<=x[0]-x[1]:
        sum=sum+1
        min=x[0]+x[1]
print(sum)

Submission status: Accepted

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

lis.sort(key=lambda x:x[1])
count = 0
tmp = - 10 ** 18
for i in lis:
    if tmp <= i[0]:
        count += 1
        tmp = i[1]

print(count)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from operator import attrgetter

class Robot:
  def __init__(self, position, length):
    self.position = position
    self.length = length

  @property
  def begin(self):
    return self.position - self.length
  
  @property
  def end(self):
    return self.position + self.length
  
  def __repr__(self):
    return '({0}, {1})'.format(self.begin, self.end)


N = int(input())

robots = []

for _ in range(N):
  x, l = map(int, input().split())
  robots.append(Robot(x, l))
  
robots.sort(key=attrgetter('end'))

selected = []

for robot in robots:
  if len(selected) < 1:
    selected.append(robot)
    continue

  if robot.begin >= selected[-1].end:
    selected.append(robot)
  
print(len(selected))

Submission status: Accepted

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


p.sort()
mr = -10**10
for l, r in p:
  if l >= mr:
    mr = r
    continue
  n -= 1
  mr = min(mr, r)

print(n)

Submission status: Accepted

Solution code:
n=int(input())
x=[0]*n
L=[0]*n
lis=[]

for i in range(n):
  x[i],L[i]=map(int,input().split())
  lis.append([x[i]-L[i],x[i]+L[i]])
lis.sort(key= lambda x:x[1])
tmp=-10**18
ct=0
for x in lis:
  if x[0]>=tmp:
    ct+=1
    tmp=x[1]
    
print(ct)

Submission status: Accepted

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

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

cnt = 1
current_end = robots[0][1]
for i in range(1, n):
    if current_end <= robots[i][0]:
        cnt += 1
        current_end = robots[i][1]

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

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

l, r = 0, 1
cnt = 1
while r < n:
    if robot_arms[l][1] <= robot_arms[r][0]:
        l = r
        r += 1
        cnt += 1
    else:
        r += 1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

p = []
for i in range(N):
  a,b = map(int,input().split())
  p.append([max(0,a - b),a + b])
  
q = sorted(p,key=lambda x:x[1])  

cnt = 0
d = q[0][1]
for j,k in q[1:]:
  if j < d:
    cnt += 1
  else:
    d = k

print(N-cnt)

Submission status: Accepted

Solution code:
n=int(input())
XL=[list(map(int,input().split())) for i in range(n)]
Range=[[x-l,x+l] for x,l in XL]
ans,end=0,-1*(10**9+1)
Range.sort(key=lambda X: X[1])

for R in Range:
  if end > R[0]:
    continue
  ans += 1
  end=R[1]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
Range=[]
ans,end=0,-1*(10**9+1)
for i in range(n):
  x,y=list(map(int,input().split()))
  Range.append([x-y,x+y])
Range.sort(key=lambda X: X[1])

for R in Range:
  if end <= R[0]:
    ans += 1
    end=R[1]
  else:
    continue
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
Y=[list(map(int,input().split())) for i in range(n)]
range=[]
ans,end=0,-1*(10**9+1)
for X in Y:
  range.append([X[0]-X[1],X[0]+X[1]])
range.sort(key=lambda X: X[1])

for R in range:
  if end <= R[0]:
    ans += 1
    end=R[1]
  else:
    continue
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XL = [tuple(map(int, input().split())) for _ in range(N)]
XL.sort(key=lambda p:(p[0]+p[1]))
L = -10 ** 10
ans = 0
for x, l in XL:
    if L <= x - l:
        L = x + l
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import namedtuple

Robot = namedtuple('Robot', ['end_pos', 'start_pos'])

class Solver:
    def __init__(self, n, robots):
        self.n = n
        self.robots = robots

    def order_by_endpos(self, robots):
        return map(lambda x:Robot(x[0], x[1]), sorted(map(lambda x:(x[0]+x[1], max(x[0]-x[1], 1)), robots)))

    def solve(self):
        current_pos = 0
        keep = 0
        for r in self.order_by_endpos(self.robots):
            if current_pos <= r.start_pos:
                keep += 1
                current_pos = r.end_pos
        return keep


if __name__ == "__main__":
    n = int(input())
    robots = []
    for _ in range(n):
        robots.append(tuple(map(int, input().split())))

    s = Solver(n, robots)
    print(s.solve())

Submission status: Accepted

Solution code:
class Solver:
    def __init__(self, n, robots):
        self.n = n
        self.robots = robots

    def order_by_endpos(self, robots):
        return sorted(map(lambda pos_armrange:(pos_armrange[0] + pos_armrange[1], max(pos_armrange[0] - pos_armrange[1], 1)), robots))

    def solve(self):
        current_pos = 0
        keep = 0
        for r in self.order_by_endpos(self.robots):
            start_pos = r[1]
            end_pos = r[0]
            if current_pos <= start_pos:
                keep += 1
                current_pos = end_pos
        return keep


if __name__ == "__main__":
    n = int(input())
    robots = []
    for _ in range(n):
        robots.append(tuple(map(int, input().split())))

    s = Solver(n, robots)
    print(s.solve())

Submission status: Accepted

Solution code:
N = int(input())
ST = []
for _ in range(N):
    x, l = map(int, input().split())
    ST.append((x - l, x + l))
ST.sort(key=lambda x: x[1])
# print(ST)
cur = float('-inf')
cnt = 0
for i in range(N):
    if cur <= ST[i][0]:
        cnt += 1
        cur = ST[i][1]
print(cnt)

Submission status: Accepted

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

SE = []
for x, l in XL:
    s = x - l
    e = x + l
    SE.append([s, e])

SE.sort(key=lambda x:x[1])
# print(SE)

cnt = 1
st = SE[0][1]
for s, e in SE[1:]:
    if st <= s:
        cnt += 1
        st = e
print(cnt)