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())
robot=[]
for i in range(n):
	x,l=map(int,input().split())
	robot.append([x,l])
robot.sort()
ans=1
for i in range(n-1):
	if robot[i][0]+robot[i][1]>robot[i+1][0]-robot[i+1][1]:
		if robot[i][0]+robot[i][1]<robot[i+1][0]+robot[i+1][1]:
			robot[i+1]=robot[i]
	else:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

ans = 0
cur = - (1<<60)

for i in r:
    if cur > i[0]:
        continue
    ans += 1
    cur = i[1]

print(ans)

Submission status: Accepted

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

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

segment.sort(key=lambda seg: seg[1])

ans = 0
curr_time = -1

for i in range(N):
    if curr_time < segment[i][0]:
        curr_time = segment[i][1] - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
    N = I()
    ARM = []
    for i in range(N):
        X,L = LI()
        ARM.append([X-L,X+L])
    ARM.sort(key=lambda x: x[0])
    ARM.sort(key=lambda x: x[1])

    cur = -1 * (10**10)
    ans = 0

    for i in range(N):
        if cur <= ARM[i][0]:
            ans += 1
            cur = ARM[i][1]

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
##貪欲法(greedy)
#区間スケジューリング
#B - Robot Arms

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

lst.sort(key=lambda x: x[3])
ans = []
ans.append(lst[0])

for i in range(1,n):
    if ans[-1][3] <= lst[i][2]:
        ans.append(lst[i])

print(len(ans))

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())

XL = []
for i in range(N):
    x, l = [int(_) for _ in stdin.readline().rstrip().split()]
    XL.append([x-l, x+l])
XL = sorted(XL, key=lambda x: x[1])

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

Submission status: Accepted

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

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

result = 0
cur_pos = -1000000000

for min,max in m_list:
    if cur_pos <= min:
        result += 1
        cur_pos = max
print(result)

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])
ans = 0
now = -10 ** 10
for a,b in lis:
    if now <= a:
        ans += 1
        now = b
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robot = []
for _ in range(N):
  r = []
  x, l = map(int, input().split())
  a = x + l
  b = x - l
  r += [a, b]
  robot.append(r)
Robot = sorted(robot)
 
robot_count = [Robot[0]]
for i in range(1, N):
  if Robot[i][1] >= robot_count[-1][0]:
    robot_count.append(Robot[i])
 
print(len(robot_count))

Submission status: Accepted

Solution code:
n = int(input())
List = [[0 for i in range(3)] for j in range(n)]
for i in range(n):
    robot, arm = map(int, input().split())
    List[i][0] = robot - arm # LeftEnd
    List[i][1] = robot # Center
    List[i][2] = robot + arm # RightEnd

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

now_rightend = sorted_List[0][2]
counter = 1

for i in range(n):
    if sorted_List[i][0] >= now_rightend:
        now_rightend = sorted_List[i][2]
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N=ii()
    rs = []
    for _ in range(N):
        x, l = mis()
        rs.append((x-l, x+l))
    rs.sort(key=lambda t: t[1])
    ans = 0
    right = rs[0][0] - 1
    for r in rs:
        if right <= r[0]:
            ans += 1
            right = r[1]
    print(ans)

main()

Submission status: Accepted

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

N = int(input())
XL = []
for _ in range(N):
    tmp = [int(x) for x in input().split()]
    XL.append(tmp)
LR = []
for i in XL:
    LR.append([i[0] - i[1], i[0] + i[1]])
LR.sort()
ans = N
last = LR[0][1]
for i in range(1, N):
    if last > LR[i][0]:
        if last > LR[i][1]:
            last = LR[i][1]
        ans -= 1
    else:
        last = LR[i][1]
print(ans)

Submission status: Accepted

Solution code:
MAX_V = 10**9

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 = -MAX_V
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:
class Robot:
    def __init__(self, left, right):
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        return self.right < other.right

n = int(input().rstrip())
robos = [None] * n

for i in range(n):
    line = input().rstrip().split(' ')
    robos[i] = Robot(int(line[0]) - int(line[1]), int(line[0]) + int(line[1]))

robos.sort()

cur = -1000000000
ans = 0
for i in range(n):
    if cur <= robos[i].left:
        ans += 1
        cur = robos[i].right

print(ans)

Submission status: Accepted

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

for i in range(n):
    rb.append(list(map(int, input().split())))

# print(rb)
rmSet = set()

# rb.sort(key=lambda x:x[0])
rb.sort()
r = rb[0][0] + rb[0][1]

# print(rb)
prevIdx = 0

for i in range(1, n):
    # print(i, r)
    l1 = rb[i][0] - rb[i][1]

    # Skip if not overlapped with previous one
    if l1 >= r:
        r = rb[i][0] + rb[i][1]
        continue

    r1 = rb[i][0] + rb[i][1]

    # Remove self if r is bigger than previous one
    if r1 > r:
        # print('(A) remove:', rb[i][0])
        rmSet.add(rb[i][0])
    else:
        # print('(B) remove:', rb[prevIdx][0])
        r = r1
        rmSet.add(rb[prevIdx][0])
        prevIdx = i
        # print('(B) remove:', rb[i - 1][0])
        # r = r1
        # rmSet.add(rb[i - 1][0])

# print('rmSet:', rmSet)
print(n - len(rmSet))

Submission status: Accepted

Solution code:
N=int(input())
A=[]
ans=1
for i in range(N):
    Xi,Li=map(int,input().split())
    A.append([Xi-Li,Xi+Li])
A.sort(key=lambda x:x[1])

def interf(A1,A2):
    if A1[1]>A2[0]:
        return 1
    else:
        return 0
    
pre=A[0]
for i in range(1,N):
    if interf(pre,A[i])==0:
        ans+=1
        pre=A[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

n = int(readline())
xl = [list(map(int, readline().decode('utf-8').split())) for _ in range(n)]
LR = [(x - l, x + l) for x, l in xl]
LR.sort(key=itemgetter(1))

acc = -10**18

cnt = 0

for l, r in LR:
    if acc > l:
        continue
    cnt += 1
    acc = r

print(cnt)

Submission status: Accepted

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

x = []*n
y = []*2

ans = 0

for i in range(n):
  y.append(h[i][0]-h[i][1]) #腕が届く地点の最小値
  y.append(h[i][0]+h[i][1]) #腕が届く地点の最大値
  x.append(y) #xに保存
  y = []*2 #yを初期化

x.sort(key = lambda x:x[1]) #腕が届く地点の最大値が小さい順にソート

con = -10 ** 10

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

print(ans)

Submission status: Accepted

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

x = []*n
y = []*2

for i in range(n):
  y.append(h[i][0]-h[i][1]) #腕が届く地点の最小値
  y.append(h[i][0]+h[i][1]) #腕が届く地点の最大値
  x.append(y) #xに保存
  y = []*2 #yを初期化

x.sort(key = lambda x:x[1]) #腕が届く地点の最大値が小さい順にソート

k = 0	#配列xのtale

for i in range(n-1):
  if x[k][1] > x[k+1][0]: #k番目の最大値よりもk+1の最小値の方が小さい時(つまり腕が重なる時)
    x.pop(k+1) #k+1番目を取り出す

  else:
    k += 1 #taleを一個後ろに下げる

print(len(x)) #要素数(残ったロボットの数)を出力

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

arm = xl[0][1] 
cnt = 1
for i in range(1,n):
    x,l = xl[i][0],xl[i][1]

    if arm <= xl[i][0]:
        arm = xl[i][1]
        cnt +=1
        
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline  #文字列入力では注意！
from bisect import bisect
N = int(input())
XL = [list(map(int,input().split())) for _ in range(N)]
S = []
for x,l in XL:
    S.append([x-l,x+l])

S.sort(key=lambda x: x[1])
ans = 1
mi = S[0][1]
for i in range(1,N):
    if mi <= S[i][0]:
        mi = S[i][1]
        ans += 1
print(ans)

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.sort(key=lambda x: x[1])
ans = 0
lon = -(10 ** 9)
for i in range(n):
    if lon <= arm[i][0]:
        lon = arm[i][1]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
U = []
for i in range(N):    
    x, l = (map(int,input().split()))
    u = [x+l,x-l]
    U.append(u)
U.sort()

ans = 1
x = U[0][0]
for i in range(N-1):
    if U[i+1][1] >= x:
        ans += 1
        x = U[i+1][0]
print(ans)

Submission status: Accepted

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

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])
 
ans=1
bef=L[0][1]
for i in range(1,n):
    if bef<=L[i][0]:
        bef=L[i][1]
        ans+=1
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])

ans=1
border=L[0][1]

for i,j in enumerate(L[1:]):
    if border<=j[0]:
        ans+=1
        border=j[1]
print(ans)

Submission status: Accepted

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

rng.sort()
count = 1
border = rng[0][0]


for i, j in enumerate(rng[1:]):
    if border <= j[1]:
        count += 1
        border = j[0]
print(count)

Submission status: Accepted

Solution code:
N = int(input())
XL = []
for i in range(N):
	x,l = map(int,input().split())
	S = x + l
	T = x - l
	XL.append((S,T))
XL.sort()
#print(XL)

ans = 0

min = -float("inf")
for s,t in XL:
	if min <= t:
		ans+=1
		min = s
print(ans)

Submission status: Accepted

Solution code:
def b_robot_arms():
    from operator import itemgetter
    N = int(input())
    Robots = [[int(i) for i in input().split()] for j in range(N)]

    robot_arms = sorted([[x - l, x + l] for x, l in Robots], key=itemgetter(1))
    current = -float('inf')
    ans = 0
    for left, right in robot_arms:
        if current <= left:
            ans += 1
            current = right
    return ans

print(b_robot_arms())

Submission status: Accepted

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

Submission status: Accepted

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

hq = []
heapq.heapify(hq)  # リストhqのheap化
for i in range(N):
    X, L = map(int, input().split())
    heapq.heappush(hq, (X+L, X-L))  # heap化されたリストhqに要素xを追加

T = -10**10
ans = 0
for i in range(N):
    t, s = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    # print(t, s, T)
    if s >= T:
        ans += 1
        T = t
print(ans)

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n = ni()
p = [na() for i in range(n)]
d = [[0, 0] for i in range(n)]
for i in range(n):
    d[i][0] = p[i][0] + p[i][1]
    d[i][1] = p[i][0] - p[i][1]

d.sort()

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

print(ans)

Submission status: Accepted

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

sch.sort()
ans = 0
t = -float('inf')
for ed, st in sch:
    if t <= st:
        ans += 1
        t = ed
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:
def solve():
    n = int(input())
    XL = [list(map(int, input().split())) for _ in range(n)]
    ps = sorted((x + l, x - l) for x, l in XL)
    ans = 1
    last = ps[0][0]
    for s, t in ps[1:]:
        if last <= t:
            ans += 1
            last = s
    print(ans)
solve()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[]

  for _ in range(n):
    a,b=LI()
    l.append([a-b,a+b])

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

  t=-inf
  ans=0
  for a,b in l:
    if t<=a:
      t=b
      ans+=1

  return ans

# main()
print(main())

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

count = 0
max_arm = -float("inf")
for robo in robots:
    if robo[0] < max_arm:
        count += 1
    else:
        max_arm = robo[1]

print(N - count)

Submission status: Accepted

Solution code:
N = int(input())
XL = sorted([list(map(int,input().split())) for _ in range(N)], key=lambda x: x[0]+x[1])
n = 1
S_,T_ = XL[0][0]-XL[0][1], XL[0][0]+XL[0][1]
for i in range(1,N):
  S,T = XL[i][0]-XL[i][1], XL[i][0]+XL[i][1]
  if not (S < T_):
    n += 1
    S_,T_ = S,T
print(n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, X: "List[int]", L: "List[int]"):
    tmp = []
    for i in range(N):
        tmp.append((X[i] + L[i], X[i] - L[i]))
    tmp.sort()
    cur = tmp[0][1] - 1
    ret = 0
    for i in range(N):
        if cur <= tmp[i][1]:
            ret += 1
            cur = tmp[i][0]
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    L = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        L[i] = int(next(tokens))
    solve(N, X, L)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read

N, *XL = map(int, read().split())

seq = [(X - L, X + L) for X, L in zip(*[iter(XL)] * 2)]
seq.sort(key=itemgetter(1))
answer = 0
left = -10 ** 10
for i, j in seq:
    if left <= i:
        answer += 1
        left = j

print(answer)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read

N, *XL = map(int, read().split())
seq = []

for X, L in zip(*[iter(XL)] * 2):
    seq.append((X - L, X + L))

seq.sort(key=itemgetter(1))
answer = 0
left = -10 ** 10
for i, j in seq:
    if left <= i:
        answer += 1
        left = j

print(answer)

Submission status: Accepted

Solution code:
n = int(input())

arms = []
for i in range(n):
  x, l = [int(i) for i in input().split(' ')]
  arms.append({"st": x-l, "ed": x+l})

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

n_arm = 1
tot_end = arms[0]["ed"]

for i in range(1, n):
  if tot_end <= arms[i]["st"]:
    n_arm += 1
    tot_end = arms[i]["ed"]

print(n_arm)

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 = -10**9
removed = 0
for x, l in XL:
    if x-l < right:
        removed += 1
    else:
        right = x+l
print(N-removed)

Submission status: Accepted

Solution code:
N = int(input())
X = []
for i in range(N):
    x, l = map(int, input().split())
    s, e = x-l, x+l
    X.append((s, e))
X.sort(key=lambda x: x[1])
#print(X)
c1 = 1
n1 = X[0][1]
for i in range(1,N):
    if X[i][0] >= n1:
        c1 += 1
        n1 = X[i][1]
c2 = 0
n2 = X[0][0]
for i in range(1,N):
    if X[i][0] >= n2:
        c2 += 1
        n2 = X[i][1]
print(max(c1, c2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
cur = -10**9

ppair = [[0,0]]*N
for i in range(N):
    tmp = list(map(int,input().split()))
    ppair[i] = [tmp[0]+tmp[1],tmp[0]-tmp[1]]

ppair.sort()
ans = 0
for i in range(N):
    if (cur <= ppair[i][1]):
        ans += 1
        cur = ppair[i][0]

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
n=int(input())
data=[]
for i in range(n):
    x,l=map(int,input().split())
    data.append((x-l,x+l))
data=sorted(data,key=lambda x:x[1])
p=-10**9-1
ans=0
for i in range(n):
    if data[i][0]>=p:
        ans+=1
        p=data[i][1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 1
first = machines.pop(0)
stock_r = first[0]
for r,l in machines:
  if stock_r > l:
    continue
  else:
    ans += 1
    stock_r = r

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
rng = []
for i in range(n):
  x,l = map(int,input().split())
  rng.append([x-l,x+l])
rng.sort(key=itemgetter(1))
M = -10**9+1
ans = 0
for lst in rng:
  if lst[0] >= M:
    ans += 1
    M = lst[1]
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()

#print(ts)
ans=0
old=-10**10
for i,j in ts:
  
  if j>=old:
    old=i
  else:
    ans+=1

print(n-ans)

Submission status: Accepted

Solution code:
n = int(input())

count = 0
X = []
for i in range(n):
    x,l = map(int, input().split())
    X.append((x+l,x-l))
X.sort()
coord = -float('inf')

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

Submission status: Accepted

Solution code:
INF = 2 * (10 ** 9) - 1

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

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

cnt = 0
#print(xl)
cur = -10 ** 10
ans = 0

for i in range(n) :
    if cur+1 < xl[i][0] :
        #print(i)
        ans += 1
        cur = xl[i][1]
        #prinst(xl[i])


print(ans)

Submission status: Accepted

Solution code:
INF = 2 * (10 ** 9) - 1

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

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

cnt = 0
#print(xl)
cur = -10 ** 10
ans = 0

for i in range(n) :
    if cur <= xl[i][0] :
        #print(i)
        ans += 1
        cur = xl[i][1]
        #prinst(xl[i])


print(ans)

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()
right = -10**9

ans = 0
for r, l in li:
  if l >= right:
    right = r
    ans += 1
    
print(ans)

Submission status: Accepted

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

prev = []
ans = 0
for i in range(n):
    if not prev:
        ans += 1
        prev = l2[i]
    elif l2[i][0] >= prev[1]:
        ans += 1
        prev = l2[i]
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = []
    xl = {}
    tmp = []
    ans = 0
    maxtmp = 0
    for i in range(n):
        xx, ll = map(int,input().split())
        if maxtmp < xx:
            maxtmp = xx
        low = xx-ll
        high = xx+ll
        lmh = [high,xx,low]
        tmp.append(lmh)


    tmp.sort()
    high = tmp[0][0]
    ans = 1
    for i in range(1,len(tmp)):
        a = tmp[i]
        if a[2] >= high:
            high = a[0]
            ans += 1
        else:
            continue

    print(ans)
    return


if __name__=='__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
"""
[X-Li,X+Li)
"""
N = int(input())
rls = []
for i in range(N):
    x,l = map(int, input().split())
    rls.append((x+l,x-l))
rls.sort()
cnt = 0
r_now = -10**10
# print(rls)
for r,l in rls:
    if l >= r_now:
        cnt += 1
        r_now = r
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
MAX_list = []
ans = 0
A = -10**9-2

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

for m, l in MAX_list:
    if l >= A:
        ans += 1
        A = m

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ps = []
cur = -10 ** 18
ans = n
for i in range(n):
    x, l = map(int, input().split())
    ps.append([x - l, x + l])

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

for i in range(n):
    if ps[i][0] >= cur:
        cur = ps[i][1]
    else:
        ans -= 1
print(ans)

Submission status: Accepted

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

from operator import itemgetter

n=int(readline())
m=map(int,read().split())
robots=list(zip(m,m))
lr=[[i-j,i+j] for i,j in robots]
lr.sort(key=itemgetter(1))
prep=lr[0][1]
res=1
for l,r in lr[1:]:
  if l>=prep:
    res+=1
    prep=r
print(res)

Submission status: Accepted

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

n=int(readline())
m=map(int,read().split())
robots=list(zip(m,m))
lr=[[i-j,i+j] for i,j in robots]
lr.sort(key=lambda x:x[1])
prep=lr[0][1]
res=1
for l,r in lr[1:]:
  if l>=prep:
    res+=1
    prep=r
print(res)

Submission status: Accepted

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

x, l = xl[0]
ans = n
for i in range(1, n):
    if x+l-1 < xl[i][0]-xl[i][1]:
        x, l = xl[i]
    else:
        ans -= 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:x[0]+x[1])
ans=1
left=XL[0][0]+XL[0][1]
for i in range(1,N):
  if XL[i][0]-XL[i][1] >= left:
    ans+=1
    left=XL[i][0]+XL[i][1]
  else:
    pass
print(ans)

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()
tmp = r[0]
cnt = 0
for i in range(1, n):
    if r[i][1] < tmp[0]:
        cnt += 1
    else:
        tmp = r[i]
print(n-cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# 区間スケジューリング典型

### TESTCASE
test = ""
#test = \
"""
4
2 4
4 3
9 3
20 5
ans
3
"""

"""
5
10 1
2 1
4 1
6 1
8 1
ans
5
"""

"""
3
3 2
5 1
7 2
ans
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN
        
n = int(input2())
XL = [tuple(map(int, input2().split())) for _ in range(n)]

arms = [(x[0]+x[1], x[0]-x[1]) for x in XL]
armsx = sorted(arms, reverse=True)

varmax = -1 * 10**15
ans = 0
while armsx:
    tmp = armsx.pop()
    
    if tmp[1]+1 > varmax:
        varmax = tmp[0]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# B
N = int(input())

value = []
for _ in range(N):
    tmp1, tmp2 = map(int, input().split())
    
    a = max(0, tmp1-tmp2)
    b = tmp1+tmp2
    value.append([a,b])

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

pre_right = value[0][1]

count = 1
for i in range(1, N):
    left = value[i][0]
    right = value[i][1]
    
    if left >= pre_right:
        count+=1
        pre_right = right      

print(count)

Submission status: Accepted

Solution code:
# Keyence B

N = int(input())
robot_list = []
robot_count = 0

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

robot_list.sort()
r = - 10**9 - 1

for i in range(N):
    if r <= robot_list[i][1]:
        robot_count += 1
        r = robot_list[i][0]

print(robot_count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    X = []
    for _ in range(N):
        x, l = map( int, input().split())
        X.append((x+l-1, x-l+1))
    X.sort()
    ans = 1
    now = X[0][0]
    for i in range(1,N):
        b, a = X[i]
        if now +1< a:
            now = b
            ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    X = []
    for _ in range(N):
        x, l = map( int, input().split())
        X.append((x+l, x-l))
    X.sort()
    ans = 1
    now = X[0][0]
    for i in range(1,N):
        b, a = X[i]
        if now <= a:
            now = b
            ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N = int(input())
    lr = []
    for _ in range(N):
        p,l = map(int,input().split())
        lr.append((p-l,p+l))
        
    lr.sort(key = itemgetter(1,0))
    now = -10**10
    count = 0
    for i in range(N):
        if now <= lr[i][0]:
            count += 1
            now = lr[i][1]
        
    print(count)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
rang=[]
for _ in range(N):
  x,l=map(int,input().split())
  rang.append((x-l, x+l))
rang=sorted(rang, key=lambda x: x[1])
lastright=rang[0][1]
cnt=1
for i in range(1,N):
  left=rang[i][0]
  right=rang[i][1]
  if left>=lastright:
    cnt+=1
    lastright=right
print(cnt)

Submission status: Accepted

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

arms.sort()
ans = 0
coord = -float('inf')

for arm in arms:
  if arm[1] >= coord:
    ans += 1
    coord = arm[0]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

num_array = [[0]*2 for i in range(N)]
for i in range(N):
    x, l = map(int, input().split())
    small = x-l
    if small <= 0:
        small = 0
    big = x+l

    num_array[i][1] = small
    num_array[i][0] = big

num_array.sort()

tmp_r = -(10**18)
count = 0
for r, l in num_array:
    if tmp_r > l:
        continue
    count += 1
    tmp_r = r

print(count)

Submission status: Accepted

Solution code:
#python3
import operator as op
n = int(input())
a = []
for _ in range(n):
    x, l = map(int, input().split())
    a.append((x - l, x + l))


a.sort(key=op.itemgetter(1))

tmp = - int(1e12)
cnt = 0
for i in range(n):
    MIN, MAX = a[i]
    if tmp > MIN:
        pass
    else:
        cnt +=1
        tmp = MAX
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
XL = []
for _ in range(N):
    x,l = map(int,input().split())
    #腕の右端が左にあるものから調べる
    XL.append([x+l,x-l])
XL.sort()

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

Submission status: Accepted

Solution code:
from operator import itemgetter

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=itemgetter(1))

ans = 0
m = -float("inf")
for left, right in xl:
    if left < m:
        ans += 1
    else:
        m = max(m, right)

print(n - ans)

Submission status: Accepted

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

X_L = sorted(X_L, key=lambda x:x[1],reverse=False)
#X_L = sorted(X_L, key=lambda x:x[0],reverse=False)

#print(X_L)

right = X_L[0][1]
Sum = 1

for i in range(1,N):
    if right <= X_L[i][0]:
        Sum += 1
        right = X_L[i][1]

print(Sum)

Submission status: Accepted

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

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

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

print(ans)