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())
s = [[]]*n
for i in range(n):
    x, l = map(int,input().split())
    s[i] = [x-l, x+l]
s.sort(key = lambda x : x[1])

n = len(s)
cnt = 1

for i in range(1,n):
    if s[i-1][1] > s[i][0]:
        s[i][1] = s[i-1][1]
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n = I()
    ranges = []
    for i in range(n):
        x, l = LI()
        ranges.append([x - l, x + l])
    ranges.sort(key=lambda x: x[1])
    ans = n
    for i in range(1, n):
        if ranges[i - 1][1] > ranges[i][0]:
            ans -= 1
            ranges[i][1] = ranges[i - 1][1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
se = [[]] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = [x-l, x+l]
se = sorted(se, key=lambda x: x[1])
ans = N
for i in range(1, N):
	if se[i-1][1] > se[i][0]:
		se[i][1] = se[i-1][1]
		ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
pos_list = [[0] * 2 for i in range(N)]
for i in range(N):
    X, L = map(int, input().split())
    pos_list[i] = [X + L, X - L]
    # pos_list.append([X + L, X - L])
sorted_data = sorted(pos_list)
# print(pos_list)
ans = 0
current = -(10 ** 9)
for val in sorted_data:
    if current <= val[1]:
        ans += 1
        current = val[0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
pos_list = []
for _ in range(N):
    X, L = map(int, input().split())
    pos_list.append([X + L, X - L])
sorted_data = sorted(pos_list)
# print(pos_list)
ans = 0
current = -(10 ** 9)
for val in sorted_data:
    if current <= val[1]:
        ans += 1
        current = val[0]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

intervals = []

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

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

cnt = n
lastEnd = intervals[0][1]

for i in range(1, n):
    if intervals[i][0] < lastEnd:
        cnt -= 1
    else:
        lastEnd = intervals[i][1]

print(cnt)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    span = [None for _ in range(n)]
    for i in range(n):
        x, l = LI()
        span[i] = [x-l, x+l]
    span.sort(key=lambda x: x[1])
    choice = [[-float("inf"),-float("inf")]]
    for each_span in span:
        if choice[-1][1] <= each_span[0]:
            choice.append(each_span)
    
    ans = len(choice)-1
    print(ans)
main()

Submission status: Accepted

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

for i in range(N):
  dist[i][0] = arm[i][0] + arm[i][1]
  dist[i][1] = arm[i][0]
  dist[i][2] = arm[i][1]

dist.sort()

ans = 1
left = dist[0][1] + dist[0][2]
for i in range(1, N):
  if left <= dist[i][1] - dist[i][2]:
    ans += 1
    left = dist[i][1] + dist[i][2]

print(ans)

Submission status: Accepted

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

d=[1,sum(rb[0])]
for i in range(1,len(rb)):
  if sum(rb[i])<d[1]:
    d[1]=sum(rb[i])
  elif rb[i][0]-rb[i][1]>=d[1]:
    d[0]+=1
    d[1]=sum(rb[i])
print(d[0])

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for _ in range(n):
    i,j=map(int,input().split())
    a+=[[i+j,i-j]]
a.sort()
b,c=-10**9,0
for i,j in a:
    if j>=b:
        c+=1
        b=i
print(c)

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])
from operator import itemgetter

W=sorted(X, key=itemgetter(1))

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

for s, e in W:
	if s>=last:
		last=e
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
INF=10**20
 
X=[]
for i in range(N):
  x,l=map(int,input().split())
  X.append((x-l,x+l-1))
  
X = sorted(X,key=lambda x:x[1])

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

Submission status: Accepted

Solution code:
from collections import deque
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])
L = deque(L)
s, ans = -10**8, 0
while L:
  l = deque.popleft(L)
  if s<=l[0]:
    ans += 1
    s = l[1]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
b=[[a[i][0]+a[i][1],a[i][0]-a[i][1]] for i in range(n)]
b.sort()
ans=1
tmp=b[0][0]
for i in range(n):
  if tmp<=b[i][1]:
    ans+=1
    tmp=b[i][0]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
XL=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x: x[0]+x[1])
r,a=-10**9,0
for x,l in XL:
    if r<=x-l:
        a+=1
        r=x+l
print(a)

Submission status: Accepted

Solution code:
n = int(input())

robot_list = []

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

delete_robot = 0
robot_list.sort()
temp_robot = robot_list[0]

for i in range(n-1):
    if temp_robot[0] > robot_list[i+1][1]:
        delete_robot += 1
    else:
        temp_robot = robot_list[i+1]

print(n - delete_robot)

Submission status: Accepted

Solution code:
# 多次元リストの sort に使える
from operator import itemgetter

n = int(input())
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = map(int, input().split())

st = sorted([(x[i] - l[i], x[i] + l[i]) for i in range(n)], key = itemgetter(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:
from operator import itemgetter
n = int(input())
lis = []
for _ in range(n):
    x,l = map(int,input().split())
    lis.append([x-l,x+l])
lis.sort(key = itemgetter(1))
ans = 0
last = -float("inf")
for i in range(n):
    if lis[i][0] >= last:
        ans += 1
        last = lis[i][1]
print(ans)

Submission status: Accepted

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

XL = [[x-l, x+l] for x,l in xl]
XL.sort(key=lambda x: x[1])

now = -float("inf")
ans = 0
for left, right in XL:
    if now <= left:
        now = right
        ans += 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,sections=int(input()),[]

for i in [0]*N:
    x,l=map(int,input().split())
    sections.append((x+l,x-l))

sections.sort()

res=N
r,l=sections.pop(0)
for nr,nl in sections:
    if nl<r:
        res-=1
    else:
        r=nr
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = []
    for _ in range(n):
        x, l = map(int, input().split())
        A.append([x - l, x + l])
    A.sort(key = lambda x: x[1])
    ans, lmax = 0, -10 ** 11
    for a in A:
        if lmax <= a[0]:
            ans += 1
            lmax = a[1]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    robot.sort(key=lambda x: x[1])
    cnt = 1
    l = robot[0][1]
    for i in range(1,N):
        if l <= robot[i][0]:
            cnt += 1
            l = robot[i][1]

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

K=0
x=-float("inf")

for a,b in A:
    if x<=a:
        K+=1
        x=b

print(K)

Submission status: Accepted

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

l_list = sorted(l_list, key=lambda a:a[1])
# print(l_list)
t = l_list[0][1]
ans = 1
for i in range(1, n):
    s = l_list[i][0]
    if s < t:
        continue
    t = l_list[i][1]
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
items = [list(map(int, input().split())) for i in range(N)]
items = sorted(items, key=lambda x:x[0]+x[1])
res = 0
bf =  -10**9
for x, l in items:
    if bf <= x - l:
        res += 1
        bf = x + l
print(res)

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
M,*li = [list(map(int,i.split())) for i in open(0)]
M = M[0]
row = [[x-y,x+y] for x,y in li]
row.sort(key = lambda x:x[1])
ans = 0
s = -1*float('inf')
for rs,rt in row:
    if s <= rs:
        ans += 1
        s = rt
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
t = lst[0][0]-1
for i in range(N):
  if t <= lst[i][0]:
    ans += 1
    t = lst[i][1]
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
A = [0] * N
for i in range(N):
    x, l = map(int, input().split())
    A[i] = (x - l, x + l)
A = sorted(A, key=lambda x: x[1])

last = -INF
ans = 0
for l, r in A:
    if l < last:
        continue
    ans += 1
    last = r
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
xl=[list(map(int,input().split()))for _ in range(N)]
rl=[[x+l,x-l]for x,l in xl]
rl.sort()
now=-10**9
ans=0
for r,l in rl:
    if l>=now:
        ans+=1
        now=r
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
xl=[list(map(int,input().split()))for _ in range(N)]
arms={}
for x,l in xl:
    arms[x-l]=0
    arms[x+l]=0
for x,l in xl:
    arms[x-l]+=1
    arms[x+l]-=1
point={}
for x,l in xl:
    point[x-l]=[]
    point[x+l]=[]
for x,l in xl:
    point[x-l].append(x+l)

ans=N
K=sorted(arms.keys())
now=0
count=[]
for k in K:
    now+=arms[k]
    for kk in point[k]:
        count.append(kk)
    for i in range(count.count(k)):
        count.remove(k)
    if now>=2:
        ans-=now-1
        now=1
        C=sorted(count)[::-1]
        for c in C[:-1]:
            arms[c]+=1
            count.remove(c)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
edge_ls = [0] * n
for i in range(n):
    x,l = map(int,input().split())
    r = x+l
    left = x-l
    edge_ls[i] = [left,r]
edge_ls.sort(key=lambda x : x[1])
ans = 1
last = edge_ls[0][1]
for i in range(1,n):
    if last <= edge_ls[i][0]:
        ans += 1
        last = edge_ls[i][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N = NI()
    XL = [NLI() for _ in range(N)]
    
    #print(XL)
    arm_range = []
    for n in range(N):
        arm_range.append([XL[n][0]-XL[n][1],XL[n][0]+XL[n][1]])
    #print(arm_range)
    
    sorted_arm_range = sorted(arm_range, key=lambda x: x[1])  #[1]に注目してソート
    #print(sorted_arm_range)
    
    ans = 1
    arm_end = sorted_arm_range[0][1]
    
    if N == 1:
        ans = 1
    else:
        for n in range(N-1):
            if sorted_arm_range[n+1][0] >= arm_end:
                arm_end = sorted_arm_range[n+1][1]
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
rng = [[] for _ in range(n)]
for i in range(n):
  x,l=map(int,input().split())
  rng[i] = [x-l,x+l]
rng.sort(key=lambda y:y[1])
cnt=0
t_mx=-(10**10)
for i in range(n):
  if t_mx > rng[i][0]:
    cnt += 1
  else:
    t_mx = rng[i][1]
print(n-cnt)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from operator import itemgetter
N, *A = map(int, open(0).read().split())
X = [(x-l, x+l) for x, l in zip(*[iter(A)]*2)]
X.sort(key=itemgetter(1))
ans = 0
R = -float('inf')
for l, r in X:
    if R <= l:
        ans += 1
        R = r
print(ans)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
X = [(x-l, x+l) for x, l in zip(*[iter(A)]*2)]
X.sort()
ans = 1
L, R = X[0]
for l, r in X[1:]:
    if R <= l:
        ans += 1
        L = l
        R = r
    elif R > r:
        R = r
print(ans)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


N = int(input())

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

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

ans = 0
cur = -1e9
for i in range(N):
    if cur <= XL[i][0]:
        ans += 1
        cur = XL[i][1]
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])

ans = 0
cur = -1e9
for i in range(N):
    s, t = ST[i]
    if cur <= s:
        ans += 1
        cur = t
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])

ans = 0
cur = -1e9
for i in range(N):
    S, T = ST[i]
    if cur <= S:
        ans += 1
        cur = T
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

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

last = robo[0][1]
cnt = 1
for r in robo[1:]:
    if r[0] >= last:
        cnt += 1
        last = r[1]

print(cnt)

Submission status: Accepted

Solution code:
# お尻から見ていってはやく終わるを数え上げれば良い
N = int(input())
data = []
for _ in range(N):
    X, L = map(int, input().split())
    data.append((X-L, X+L))
data = sorted(data, key=lambda x: x[1])
count = 1
j = 0
for i in range(1, N):
    if data[i][0] >= data[j][1]:
        j = i
        count += 1
print(count)

Submission status: Accepted

Solution code:
def Schedule(schedule):
    """
    :return: 複数の区間が与えられた時の重複の無い区間の選び方の最大数
    """
    schedule = sorted(schedule, key=lambda x: x[1])
    N = len(schedule)
    res = 0
    end = -float("inf")

    for i in range(N):
        if end <= schedule[i][0]:  # 重複がダメならば等号を消す
            end = schedule[i][1]  # 終点でソートされているので、自動的に可能な中で最速の終点が選ばれている
            res += 1
    return res

################################################################################

import sys
input = sys.stdin.readline

N = int(input())
schedule = []
for i in range(N):
    x, l = map(int, input().split())
    schedule.append((x - l, l + x))             # schedule = (始点、終点)

print(Schedule(schedule))

Submission status: Accepted

Solution code:
n=int(input())
A=[[] for i in range(n)]
for i in range(n):
    x,l=map(int,input().split())
    A[i]=[x-l,x+l]
A=sorted(A, key=lambda x :x[1])
#print(A)

ans=0
last=-float("INF")
for i in range(n):
    if last<=A[i][0]:
        ans+=1
        last=A[i][1]

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50



def run():
    N = int(sysread())
    XL = []
    for i in range(N):
        x,l = map(int, sysread().split())
        XL.append((x-l, l+x))
    XL = sorted(XL, key = lambda x:x[1])
    #print(XL)
    ans = 0
    pre_end = - (1 << 50)
    for left,right in XL:
        if pre_end <= left:
            ans += 1
            pre_end = right
    print(ans)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[8]:


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


# In[12]:


mylist = sorted(mylist,key=lambda x:x[1])
cnt = 1
p = mylist[0][1]
for i in range(1,N):
    if mylist[i][0] < p:
        continue
    else:
        cnt += 1
        p = mylist[i][1]
print(cnt)


# In[ ]:

Submission status: Accepted

Solution code:
n=int(input())
itv=[]
for i in range(n):
  x,l=map(int,input().split())
  itv+=[(x+l,x-l)]
itv=sorted(itv)
l=-10**18
cnt=0
for t,s in itv:
  if l<=s:
    l=t
    cnt+=1
print(cnt)

Submission status: Accepted

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

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

end = -maxsize

res = 0

for arm in arms:
    if end <= arm[0]:
        res += 1
        end = arm[1]
print(res)

Submission status: Accepted

Solution code:
n = int(input())
A = []
for i in range(n):
    x, l = map(int, input().split())
    a = x - l
    b = x + l
    A.append((a, b))
A = sorted(A, key = lambda x:x[1])
cnt = 0
right = -float('inf')
for i in range(n):
    if right <= A[i][0] :
        cnt += 1
        right = A[i][1]
print(cnt)

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.sort(key=lambda x: x[1])

ans = 1
for i in range(N):
    if (i == 0):
        first = R[0][1]
        continue

    if first <= R[i][0]:
        first = R[i][1]
        ans += 1

print(ans)

Submission status: Accepted

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

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

R.sort()

l = -(1 << 40)

cnt = 0
for r in R:
    if l <= r[1]:
        cnt += 1
        l = r[0]

print(cnt)

Submission status: Accepted

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

t = [(x + l, x - l) for x, l in XL]
t.sort()
max_r = -float('inf')
result = 0
for i in range(N):
    r, l = t[i]
    if max_r <= l:
        result += 1
        max_r = r
print(result)

Submission status: Accepted

Solution code:
N=int(input())

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

answer=0
max_r=-float("inf")
for r,l in rllist:
  #print(max_r,l)
  if max_r<=l:
    answer+=1
    max_r=r
  
print(answer)

Submission status: Accepted

Solution code:
N=int(input())

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

answer=0
max_r=-float("inf")
for r,l in rllist:
  #print(max_r,l)
  if max_r<=l:
    answer+=1
    max_r=max(max_r,r)
  
print(answer)

Submission status: Accepted

Solution code:
import bisect
N=int(input())

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

dp=[0]*N
for i in range(N):
  r,l=rllist[i]
  
  pos=bisect.bisect(rllist,(l,float("inf")))
  #print(i,pos)
  dp[i]=max(dp[i-1],dp[pos-1]+1)
  
#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
import bisect
N=int(input())

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

dp=[0]*N
dp[0]=1
for i in range(1,N):
  r,l=rllist[i]
  
  pos=bisect.bisect(rllist,(l,float("inf")))
  #print(i,pos)
  if pos==0:
    dp[i]=dp[i-1]
  else:
    dp[i]=max(dp[i-1],dp[pos-1]+1)
  
#print(dp)
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
robot = list(list(map(int, input().split(' '))) for i in range(n))

for i in range(n):
  robot[i].append(robot[i][0]-robot[i][1])
  robot[i].append(robot[i][0]+robot[i][1])

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

ans=1
left=robot[0][2]
right=robot[0][3]
for i in range(1,n):
  if robot[i][2]>=right:
    ans+=1
    right=robot[i][3]
    
    
print(ans)

Submission status: Accepted

Solution code:
rs = [(x - l, x + l) for x, l in (map(int, input().split()) for _ in range(int(input())))]
rs.sort(key=lambda x: x[1])
last = - 10 ** 9
ans = 0
for l, r in rs:
    if last <= l:
        ans += 1
        last = r
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = []
for i in range(N):
  X, L = map(int, input().split())
  l.append([X-L, X+L])
  
l.sort(key=lambda x: x[1])
pin = l[0][1]
ans = 1

for i in range(1, N):
  if pin <= l[i][0]:
    ans += 1
    pin = l[i][1]
    
print(ans)

Submission status: Accepted

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

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

res = n
pos = -float('inf')
for l, r in list_:
    if l < pos:
        res -= 1
    else:
        pos = r

print(res)

Submission status: Accepted

Solution code:
n=int(input())
lst=[list(map(int,input().split())) for i in range(n)]
lst=[[i[0]-i[1],i[0]+i[1]] for i in lst]

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

pin=lst[0][1]
ans=1

for i in range(1,n):
  if pin<=lst[i][0]:
    ans+=1
    pin=lst[i][1]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
num=[]
for i in range(n):
    x,l=map(int,input().split())
    num.append([x,l,x+l])
str1= lambda val: val[2]
num.sort(key=str1)
ans=n
num1=num[0][2]
for i in range(n-1):
    if num1>num[i+1][0]-num[i+1][1]:
        ans-=1
    else:
        num1=num[i+1][2]
print(ans)

Submission status: Accepted

Solution code:
#区間スケジューリング問題

N = int(input())

robots = {}

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

    robots[X] = (X-L, X+L)

#終端が早い順にソートして、取れるものから貪欲法でとっていく

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

ans = 1
current_robot = robots_sorted[0]

for i in range(0, N):
    if current_robot[1][1] > robots_sorted[i][1][0]:
        continue

    ans += 1
    current_robot = robots_sorted[i]


print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
ls = []
for i in range(n):
    x, l = MAP()
    ls.append([x-l, x+l])

ls = sorted(ls, key=itemgetter(1))
ans = n
for i in range(1, n):
    if ls[i][0] < ls[i-1][1]:
        ls[i][1] = ls[i-1][1]
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = [[0]*2 for i in range(n)]
for i in range(n):
    x[i][0], x[i][1] = MAP()

x.sort()
tmp = -inf
ans = n
for i in range(n):
    if tmp > x[i][0] - x[i][1]:
        ans -= 1
        tmp = min(tmp, x[i][0] + x[i][1])
    else:
        tmp = x[i][0] + x[i][1]
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    mat = []

    for _ in range(n):
        x, l = map(int, readline().split())
        left, right = x - l, x + l
        mat.append([left, right])

    mat.sort()

    i = 1
    cur_l, cur_r = mat[0]
    ans = 1

    while i < n:
        next_l, next_r = mat[i]
        if next_l < cur_r:
            if next_r < cur_r:
                cur_l, cur_r = next_l, next_r
        else:
            cur_l, cur_r = next_l, next_r
            ans += 1
        i += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sorted_table = sorted(table, key=lambda x: x[1])
# print(sorted_table)
left = sorted_table[0][1]
ans = n
for i in range(1, n):
    if left <= sorted_table[i][0]:
        left = sorted_table[i][1]
    else:
        ans -= 1

print(ans)

Submission status: Accepted

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

N = int(input())
imo = []
xlmin = 0
xlmax = 0
for _ in range(N):
    x,l = map(int,input().split())
    imo.append([x-l,x+l-1])
imo = sorted(imo,key = lambda x: x[1])
cnt = 1
ls = imo[0][1]
for i in range(1,N):
    if imo[i][0]<=ls:
        continue
    else:
        cnt += 1
        ls = imo[i][1]
print(cnt)

Submission status: Accepted

Solution code:
def main():
    import sys

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

    n = int(input())
    itv = []
    for i in range(n):
        x, l = map(int, input().split())
        itv.append((x+l, x-l))
    itv.sort()
    r = - 10 ** 12
    cnt = 0
    for x in itv:
        if r <= x[1]:
            cnt += 1
            r = x[0]
    
    print(cnt)

    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


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

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

b = []
e = []
for i in np.argsort(ends):
    b.append(begins[i])
    e.append(ends[i])
begins = b
ends = e

now = -1e9
cnt = 0
for i in range(N):
    if now <= begins[i]:
        cnt += 1
        now = ends[i]

print(cnt)

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.sort(key=lambda x: x[1])

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

Submission status: Accepted

Solution code:
n = int(input())
xlt = []
for i in range(n):
    xi,li = map(int,input().split())
    xlt.append((xi+li,xi-li))
xlt.sort()
ans = 0
x = -float("INF")
for i in range(n):
    if x <= xlt[i][1]:
        ans += 1
        x = xlt[i][0]
print(ans)