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())

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

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

select = 0
for i in range(N):
  if i == 0:
    temp = Y[i][1] #今の終わり
    select += 1
  else:
    if Y[i][0] >= temp: #今の終わりより次の始まりの方が後ならおｋ
      temp = Y[i][1]
      select += 1
print(select)

Submission status: Accepted

Solution code:
INF = 10 ** 12

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

sections = list(map(lambda t: (t[0]-t[1], t[0]+t[1]), xls))
sections.sort(key = lambda s: s[1])

#greedy
pos = -INF
counter = 0
for section in sections:
    if pos <= section[0]:
        counter += 1
        pos = section[1]

print(counter)

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = []

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

    t = -float('inf')
    a.sort(key=lambda x: x[1])
    ans = 0

    for start_t, end_t in a:
        if t <= start_t:
            ans += 1
            t = end_t

    print(ans)

resolve()

Submission status: Accepted

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

kukan=[[s[i][0]-s[i][1], s[i][0]+s[i][1]] for i in range(n)]
kukan.sort(key=lambda x:x[1])

count=1
mae=kukan[0][1]
for i in range(1,n):
    if kukan[i][0]>=mae:
        count+=1
        mae=kukan[i][1]

print(count)

Submission status: Accepted

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

ans = N
for i in range(1, N):
    if ls[i-1][1] > ls[i][0]:
        ls[i][1] = ls[i-1][1]
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 9
MOD = 10 **9 + 7
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  collections import deque
from math import factorial

def main():
    n = int(input())
    Robot = [tuple(map(int,input().split())) for _ in range(n)]
    Robot.sort(key = lambda x: sum(x))

    ans = n
    now = -INF
    for i in range(n):
        if now <= Robot[i][0] - Robot[i][1]:
            now = sum(Robot[i])
        else:
            ans -= 1
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

selist=[]
for i in range(n):
    tmpx,tmpl = map(int,input().split())
    selist.append([tmpx-tmpl,tmpx+tmpl])

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


maeindex=0
maeza=selist[0][0]-1
robnum=0
finishflag=True



while finishflag:
	for i in range(maeindex,n):
		if selist[i][0] >= maeza:
			maeindex=i
			robnum+=1
			maeza=selist[i][1]
			break
		if i == n-1:
			finishflag=False


print(robnum)

Submission status: Accepted

Solution code:
N = int(input())
T = []
for _ in range(N):
    X,L = map(int, input().split())
    T.append([X-L,L+X])
T = sorted(T, key=lambda x:x[1])

ans = []
ans.append(T[0])
for i in range(1, N, 1):
    if ans[-1][1] <= T[i][0]:
        ans.append(T[i])

print(len(ans))

Submission status: Accepted

Solution code:
inf = float('inf')

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

st = []
for i in range(n):
    s = x[i] - l[i]
    t = x[i] + l[i]
    st.append([s, t])

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

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


print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    xs=[0]*n
    ls=[0]*n
    ranges=[0]*n
    for i in range(n):
        xs[i],ls[i]=map(int,input().split())
        ranges[i]=[xs[i]-ls[i],xs[i]+ls[i]]
    ranges.sort(key=lambda x:x[1])
    count=0
    point=-1000000000000
    for irange in ranges:
        if irange[0]>=point:
            count+=1
            point=irange[1]
    print(count)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):
    return map(type,input().split())

#%%code
def resolve():
    N=int(input())
    A=[tuple(pin())for i in range(N)]
    A.sort(key=lambda x:x[0]+x[1])
    ans=0
    jama=-10000000000#int value
    for i in range(N):
        if A[i][0]-A[i][1]>=jama:
            jama=sum(A[i])
            ans+=1
            
    print(ans)
#%%submit!
resolve()

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.sort()

hand = robots[0][0]
count = 1
for robot in robots[1:]:
  if hand <= robot[1]:
    hand = robot[0]
    count += 1
print(count)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

robot = heappop(robots)
hand = robot[0]
count = 1
while robots:
  robot = heappop(robots)
  if hand <= robot[1]:
    hand = robot[0]
    count += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
arm = []
for n in range(N):
    i, L = map(int, input().split())
    arm.append([i+L, i-L])
sarm = sorted(arm)
pre = -10**10
count = 0
for a in sarm:
    if pre <= a[1]:
        count += 1
        pre = a[0]
print(count)

Submission status: Accepted

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

for i in range(N):
    if Robot[i][0] >= now:
        ans +=1
        now = Robot[i][1]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ranges = []
for _ in range(n):
    xi, li = map(int, input().split())
    ranges.append((xi - li, xi + li))
ranges = sorted(ranges, key=lambda x: x[1])


ans = 0
cur = -int(1e18)
for i in range(n):
    if cur <= ranges[i][0]:
        ans += 1
        cur = ranges[i][1]

print(ans)

Submission status: Accepted

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

for i in range(N):
  X[i],L[i]=map(int,input().split())
  t[i]=[X[i]-L[i], X[i]+L[i]]
  
t.sort(key=lambda x:x[1])
#print(t)

pos=float("-inf")
cnt=0
for arm in t:
  if pos<=arm[0]:
    cnt +=1
    pos=arm[1]
    
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
li=[]
for i in range(N):
    x,l=map(int,input().split())
    li.append((x-l,x+l))
li.sort(key=lambda x:x[1])
cnt=0;now=-(10**10);i=0
for i in range(N):
    if(now<=li[i][0]):
        cnt+=1
        now=li[i][1]
print(cnt)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    Robot = [[] for _ in range(N)]
    for i in range(N):
        X, L = map(int, input().split())
        Robot[i] = [X - L, X + L]
    Robot = sorted(Robot, key=lambda x: x[1])
    check = -float("inf")
    cnt = 0
    for R in Robot:
        if R[0] >= check:
            check = R[1]
        else:
            cnt += 1

    print(N - cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#B
n = int(input())
robot = []
for i in range(n):
    x,l = map(int, input().split())
    ri = x - l
    le = x + l
    robot.append([ri, le])
robot.sort(key=lambda x: x[1])
# print(robot)
a = robot[0][1]
count=1
for i in range(1, n):
    if a > robot[i][0]:
        pass
    else:
        # print(robot[i])
        #残せる
        a = robot[i][1]
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

def main():
    N = int(input())
    info = [tuple(map(int, input().split())) for _ in range(N)]

    RL = sorted([(X+L, X-L) for X, L in info])
    RL = deque(RL)

    now, _ = RL.popleft()
    ans = 1
    for _ in range(N-1):
        R, L = RL.popleft()
        if now <= L:
            now = R
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

robot_list = []
for i in range(N):
    x, l = map(int,input().split())
    s = x - l
    t = x + l
    robot_list.append([s, t])

robot_list.sort(key=lambda x:x[1])
#print(robot_list)
c = robot_list[0][1]

for i in range(1,N):
    if robot_list[i][0] >= c:
        ans += 1
        c = robot_list[i][1]
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

N = int(input())
ans = N

robot_list = []
for i in range(N):
    x, l = map(int,input().split())
    s = x - l
    t = x + l
    robot_list.append([s, t])

robot_list.sort(key=lambda x:x[1])
#print(robot_list)
c = robot_list[0][1]
for i in range(1,N):
    if robot_list[i][0] < c:
        ans -= 1
        #print(robot_list[i][0], c)
    else:
        c = robot_list[i][1]
        #print(ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
robot = [0]*n
for i in range(n):
  a, b = map(int, input().split())
  robot[i] = [a+b, a-b]

robot.sort()
ans = 0
for i in range(n):
  if i == 0:
    key = robot[0][0]
    ans += 1
    continue
  if robot[i][1] < key:
    continue
  key = robot[i][0]
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

lr=[]

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

lr.sort()

cnt=0
point=lr[0][1]-1

for item in lr:
    if item[1]>=point:
        cnt+=1
        point=item[0]

print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
S=[]
for i in range(N):
    S.append(tuple(map(int,input().split())))
S_new=[]
for j in range(N):
    S_new.append((S[j][0]-S[j][1],S[j][0]+S[j][1]))
S_new.sort(key=lambda x: x[1])
#print(S)
#print(S_new)

count=1
T=S_new[0][1]
for k in range(1,N):
    if S_new[k][0]<T:
        pass
    else:
        count+=1
        T=S_new[k][1]

print(count)

Submission status: Accepted

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

for i in range(n):
	x_in, l_in = map(int, input().split())
	position.append([x_in + l_in, x_in - l_in])

position.sort()
ans = 0
t = - (10 ** 9 + 1)

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Inp = list()
for i in range(N):
    x , l = list(map(int,input().split()))
    Inp.append([x-l,x+l])
# 右腕を基準にソートする
robots = sorted(Inp, key=lambda x: x[1])
# print(robots)

ans = 0
now = -float('inf')
for left,right in robots:
    if left >= now:
        ans += 1
        now = right

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robots = []
for _ in range(N):
    x, dis = map(int, input().split())
    robots.append([x-dis,x+dis])
    
robots = sorted(robots, key=lambda x: x[1])
    
cnt = 0
now = -float("inf")
for left, right in robots:
    if left >= now:
        cnt += 1
        now = right
        
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
R=sorted([list(map(int,input().split(' '))) for i in range(N)])
ans = 1
now = R[0][0]+R[0][1]
for x,l in R[1:]:
    if now > x-l and now> x+l:
        now = x+l
    elif now <=x-l:
        ans += 1
        now = x+l
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
count=1
a=[]
for i in range(N):
  x1,l1=map(int,input().split())
  a.append([x1+l1,x1-l1])
a.sort()
migi=a[0][0]
for i in range(N):
  if(a[i][1]>=migi):
    count+=1
    migi=a[i][0]
print(count)

Submission status: Accepted

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

for i in range(N):
    X, L = XL[i]
    XL[i] = (X-L, X+L)
#print(XL)

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

right = XL[0][1]
cnt = 1
for i in range(1, N):
    if right <= XL[i][0]:
        right = XL[i][1]
        cnt += 1
print(cnt)

Submission status: Accepted

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

ans = 1
tmp = rng[0][1]
for i in range(1, n):
    l, r = rng[i]
    if tmp <= l:
        ans += 1
        tmp = r

print(ans)

Submission status: Accepted

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

kept = []
cur = 0
for i in range(1, N):
    x_cur, l_cur = xl[cur]
    x_next, l_next = xl[i]
    if x_cur + l_cur <= x_next - l_next:
        kept.append(cur)
        cur = i
    elif x_cur + l_cur > x_next + l_next:
        cur = i
kept.append(cur)

print(len(kept))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
NumRobot = int(input())
RobotList = [[int(_) for _ in input().split()] for i in range(NumRobot)]

edge_list = []
for i_coordinate, i_arm in RobotList:
    edge_list.append([i_coordinate - i_arm, i_coordinate + i_arm])

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

total_robot = 1
right_edge_compare = edge_list[0][1]

for i_left_edge, i_right_edge in edge_list[1:]:
    if i_left_edge < right_edge_compare:
        continue

    right_edge_compare = i_right_edge
    total_robot += 1

print(total_robot)

Submission status: Accepted

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

LR.sort(key=lambda x: x[0])
# print(LR)
prev_right = - 10**9 #一つ前の右端
cnt = 0
for i in range(N):
  if LR[i][0]>=prev_right: #次の左端が前の右端以上なら
    cnt += 1
    prev_right = LR[i][1]
  else:
    if LR[i][1]<prev_right:
      prev_right = LR[i][1]
  # print(prev_right)

print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
X_list = []
L_list = []
#left_pos = []
#right_pos = []
range_pos = []
for i in range(N):
    [X, L] = [int(x) for x in stdin.readline().rstrip().split()]
    X_list.append(X)
    L_list.append(L)
    range_pos.append([X+L, X-L])

range_pos.sort()

index  = 0
prev_right = -1e8
for i in range(N):
    if prev_right <= range_pos[i][1]:
        prev_right = range_pos[i][0]
        index+=1

print(index)

Submission status: Accepted

Solution code:
#キーエンスプログラミングコンテスト2022-B-Robot Arms
n = int(input())
arm = []
for i in range(n):
    r,l = map(int,input().split())
    arm.append([r+l, r-l])
    
arm.sort()

ans = 1

max_r = arm[0][0]

for i in range(n-1):
    
    if max_r <= arm[i+1][1]:
        ans += 1
        max_r = arm[i+1][0]
        

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

stop = s[0][0] + s[0][1]
ans = 1
for i in range(1,n):
    num = s[i][0]
    l = s[i][1]
    if num - l >= stop:
        ans += 1
        stop = num + l
    if num + l < stop:
        stop = num + l
    

print(ans)

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])

cnt = 1
last = ST[0][1]
for i in range(1, N):
    if ST[i][0] < last:
        continue
    else:
        cnt += 1
        last = ST[i][1]

print(cnt)

Submission status: Accepted

Solution code:
N, *L = map(int, open(0).read().split())

ls = [0]*N
i = 0
for i,(x,l) in enumerate(zip(*[iter(L)]*2)):
  ls[i] = (x+l,x-l)
ls.sort()
cur = -10**20
ans = 0
for c in ls:
  if c[1]>=cur:
    ans += 1
    cur = c[0]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 07:49:36 2020

@author: naoki
"""
N = int(input())
xl = [list(map(int, input().split())) for _ in range(N)]

left_right = [[row[0]-row[1], row[0]+row[1]] for row in xl]
left_right = sorted(left_right, key = lambda x:int(x[1]))
count = 0
now = -100000000000
for row in (left_right):
    if row[0] < now:
        continue
    else:
        count += 1
        now = row[1]
print(count)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    xl[i].append(xl[i][0]+xl[i][1])
    if xl[i][0]-xl[i][1]>0: xl[i].append(xl[i][0]-xl[i][1])
    else: xl[i].append(0)
xl = sorted(xl, key=lambda x:x[2])
res = xl[0][2]
count = 1
for i in range(1, n):
    if res <= xl[i][3]:
        count += 1
        res = xl[i][2]
print(count)

Submission status: Accepted

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

lis.sort(key=lambda x: x[1])
cnt = 0
INF = 10**9
prev_r = -INF

for l, r in lis:
    if l < prev_r:
        continue
    cnt += 1
    prev_r = r
print(cnt)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    lr = []
    for _ in range(n):
        x,l = map(int, input().split())
        lr.append((x-l, x+l))
    lr.sort(key=lambda a: a[1])
    res = 0
    cur = -10**10
    for i in range(n):
        if cur <= lr[i][0]:
            cur = lr[i][1]
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    arms.sort()

    ans = 0

    for idx, (e, s) in enumerate(arms):
        if idx == 0:
            pos = e
            ans += 1
        else:
            if pos <= s:
                ans += 1
                pos = e
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xl=[list(map(int,input().split())) for i in range(n)]
xl=[i+[i[0]-i[1],i[0]+i[1]] for i in xl] # [point,arm,left,right]
xl.sort(key=lambda x: x[3])
i=0
ans=n
while i<len(xl)-1:
  if xl[i][-1]>xl[i+1][2]:
    del xl[i+1]
    ans-=1
  else:
    i+=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
X=[[0]*3 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  X[i]=[a+b,a,b]
X=sorted(X)
l=X[0][0]
ans=1
for i in range(n):
  if X[i][1]-X[i][2]>=l:
    ans+=1
    l=X[i][0]
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
xl = [list(map(int, readline().split())) for i in range(n)]
pm = [[0] * 2 for _ in range(n)]
for i in range(n):
    pm[i][0] = xl[i][0] + xl[i][1]
    pm[i][1] = xl[i][0] - xl[i][1]
pm.sort()
ans = 1
check = pm[0][0]
for i in range(1, n):
    if check <= pm[i][1]:
        check = pm[i][0]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robot = [input().split() for i in range(N)]

le = [[int(i[0])-int(i[1]), int(i[0])+int(i[1])] for i in robot]
le.sort(key = lambda x:x[1])

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
le = [[p[0]-p[1], p[0]+p[1]] for p in xl]
le.sort(key = lambda x : x[1])

ans = 0
right = -(10 ** 9) - 1
for i in range(n):
    if right <= le[i][0]:
        ans += 1
        right = le[i][1]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
le = [[p[0]-p[1], p[0]+p[1]] for p in xl]
le.sort(key = lambda x : x[1])

ans = 0
right = -(10 ** 9) - 1
for i in range(n):
    if right <= le[i][0]:
        ans += 1
        right = le[i][1]
print(ans)

Submission status: Accepted

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

max_r = -float('inf')
result = 0

for i in range(n):
    r,l = arm[i]
    if max_r <= l:
        result += 1
        max_r = r
        
print(result)

Submission status: Accepted

Solution code:
import heapq
n = int(input())
st = []
for i in range(n):
  x,l = map(int,input().split())
  heapq.heappush(st,[x+l,x-l])
ans = 0
last = -float('inf')
while len(st) > 0:
  e, s = heapq.heappop(st)
  if last <= s:
    ans += 1
    last = e
print(ans)

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])
now = -float("inf")
ans = 0
# 選べるやつを貪欲に選ぶ
for left, right in robots:
    if left >= now:
        ans += 1
        now = right
print(ans)

Submission status: Accepted

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

X = sorted(X, key=lambda x:x[1])
a = X[0][0]-1
ans = 0
for i in range(N):
    if X[i][0] >= a:
        a =X[i][1]
        ans +=1
    else:
        continue
print(ans)

Submission status: Accepted

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

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

a=X[0][0]-1
ans=0
for i in range(n):
    if X[i][0]<a:
        continue
    else:
        a=X[i][1]
        ans+=1
        
print(ans)

Submission status: Accepted

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

R = sorted(R, key=lambda x: x[1])
tmp = R[0]
ans = [R[0]]
for i in range(1, N):
    v = R[i]
    if tmp[1] <= v[0]:
        ans.append(v)
        tmp = v

print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int,input().split())) for _ in range(n)]
for i in range(n):
    x = xl[i][0]
    l = xl[i][1]
    xl[i][0] = x+l
    xl[i][1] = x-l
#[終点、支店]
xl.sort()
ans = 1
right = xl[0][0]
for i in range(n-1):
    siten = xl[i+1][1]
    shuten = xl[i+1][0]
    if right <= siten:
        ans += 1
        right = shuten

print(ans)

Submission status: Accepted

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

ts.sort()

tmp = 0
count = 0
for n in ts:
    if tmp<=n[1]:
        count += 1
        tmp = n[0]

print(count)

Submission status: Accepted

Solution code:
N = int(input())

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

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


count = 0
max_arm_position_now = -int(1e10)
for i in range(N):
    min_arm_position_next = arms_range_list[i][0]
    if min_arm_position_next >= max_arm_position_now:
        max_arm_position_now = arms_range_list[i][1]
        count += 1


print(count)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    N = int(input())
    XL = [list(map(int, input().split())) for _ in range(N)]
    XL_re = [[xl[0] - xl[1], xl[0] + xl[1]] for xl in XL]
    XL_re = sorted(XL_re, key=lambda x: x[1])

    cnt = 0
    for i, xl in enumerate(XL_re):
        if i == 0:
            tmp = xl[1]
            cnt += 1
        else:
            if tmp <= xl[0]:
                tmp = xl[1]
                cnt += 1
    print(cnt)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
2 4
4 3
9 3
100 5"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """2
8 20
1 10"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5
10 1
2 1
4 1
6 1
8 1"""
        output = """5"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
def solve(N, XL):
    XL_re = [[xl[0] - xl[1], xl[0] + xl[1]] for xl in XL]
    XL_re = sorted(XL_re, key=lambda x: x[1])

    cnt = 0
    for i, xl in enumerate(XL_re):
        if i == 0:
            tmp = xl[1]
            cnt += 1
        else:
            if tmp <= xl[0]:
                tmp = xl[1]
                cnt += 1
    return cnt

def test():
    assert solve(4, [[2, 4], [4, 3], [9, 3], [100, 5]]) == 3

def main():
    N = int(input())
    XL = [list(map(int, input().split())) for _ in range(N)]
    ans = solve(N, XL)
    print(ans)

if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

Solution code:
N = int(input())
robo = [list(map(int, input().split())) for _ in range(N)]
robo_range = sorted(list(map(lambda x: [x[0]-x[1], x[0]+x[1]], robo)), key=lambda x: x[1])
border = -10**9-1
remain = 0

for r in robo_range:
    if r[0] >= border:
        border = r[1]
        remain += 1

print(remain)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for i in range(n)]
st = [[xl[i][0] + xl[i][1], xl[i][0] - xl[i][1]] for i in range(n)]
st.sort()
ans = 1
t = st[0][0]
for i in range(1, n):
  if st[i][1] >= t:
    ans += 1
    t = st[i][0]
print(ans)

Submission status: Accepted

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

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=sorted(xl,key=lambda x:x[1])

w=1
robot=XL[0]
for i in XL:
  if robot[1] <= i[0]:
    w+=1
    robot=i
print(w)

Submission status: Accepted

Solution code:
from collections import deque

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

p = []
for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

p = deque(p)
ex = []
ex.append(p.popleft())




for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.popleft())
  else:
    p.popleft()

print(len(ex))

Submission status: Accepted

Solution code:
from collections import deque

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

p = deque()

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(0))




for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(0))
  else:
    p.pop(0)

print(len(ex))

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])

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

ans = 1
ac_max = Robot[0][1]
for i in range(1,N):
    if ac_max <= Robot[i][0]:
        ans += 1
        ac_max = Robot[i][1]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xl = [[int(i) for i in input().split()] for j in range(n)]

xl_li = []

for i in range(n):
    xl_li.append([xl[i][0]-xl[i][1],xl[i][0]+xl[i][1]])
    
xl_li = sorted(xl_li,key=lambda xl_li:xl_li[1])

tmp = xl_li[0][1]
ans = 1

for i in range(1,n):
    if tmp <= xl_li[i][0]:
        tmp = xl_li[i][1]
        ans += 1
        
print(ans)

Submission status: Accepted

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

from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    return data.sort(key=lambda x:x[col],reverse=True)

n = int(input())
xl = [ list(myinput()) for _ in range(n) ]
# print(xl)

ls = []
for i in range(n):
    x = xl[i][0]
    l = xl[i][1]
    s = x - l
    e = x + l
    d = [s,e]
    ls.append(d)
# print(ls)
ls.sort(key=lambda x:x[1],reverse=False)
# print(ls)

count = 0
e = -1*float("inf")
for i in range(n):
    ns,ne = ls[i]
    if ns>=e:
        count += 1
        e = copy(ne)
    else:
        pass

print(count)

Submission status: Accepted

Solution code:
N=int(input())

R=[]
for i in range(N):
    x,l=map(int,input().split())
    s=x-l
    t=x+l
    R.append([s,t])
R.sort(key=lambda x:x[1])
cur=-10**9
ans=0
for i in range(N):
    if cur<=R[i][0]:
        ans+=1
        cur=R[i][1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [[0,0] for i in range(n)]
for i in range(n) :
  x,l = map(int,input().split())
  s[i][0] = x-l
  s[i][1] = x+l
  
s = sorted(s, key=lambda x: x[1])
 
sd = {}
sd[10**10*s[0][0]+s[0][1]] = 1
for i in range(1,n) :
  if s[i][0] < s[i-1][1] :
    s[i] = s[i-1]
  if not 10**10*s[i][0]+s[i][1] in sd :
    sd[10**10*s[i][0]+s[i][1]] = 1
    
print(len(sd))

Submission status: Accepted

Solution code:
n=int(input())
hani=[]
for i in range(n):
    x,l=map(int,input().split())
    hani.append([x-l,x+l])
hani2=sorted(hani)
#print(hani2)
no=0 #削除するロボット
bef=0
af=1
for i in range(n-1):
    a,b,a2,b2=hani2[bef][0],hani2[bef][1],hani2[af][0],hani2[af][1]
    if a<=a2<b:
        no+=1
        if b<b2: #前者を採用
            af+=1
        else:
            bef=af
            af+=1
    else:
        bef=af
        af+=1
print(n-no)

Submission status: Accepted

Solution code:
N = int(input())

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

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

count = 0
i = arm[0][0]
for start, end in arm:
    if start < i:
        continue
    i = end
    count += 1

print(count)