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:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
# import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    d = [na() for _ in range(n)]

    query = []

    for i, di in enumerate(d):
        s = di[0] - di[1]
        t = di[0] + di[1]
        query.append((s, 1, i))
        query.append((t, 0, i))

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

    ans = 0
    idx = -1
    for x, st, i in query:
        if st == 0:
            if idx == i:
                idx = -1
        if st == 1:
            if idx == -1:
                idx = i
            else:
                if d[idx][0] + d[idx][1] > d[i][0] + d[i][1]:
                    idx = i
                ans += 1

    print(n - ans)


if __name__ == '__main__':
    main()

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

seen = -10**10
ans = 0
for i in range(n):
  rob = XL[i]
  if seen <= rob[0]-rob[1]:
    seen = rob[0]+rob[1]
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b


class Robot(object):
    def __init__(self, data):
        self.x = int(data[0])
        self.l = int(data[1])
        self.low = self.x - self.l
        self.high = self.x + self.l

    def contain(self, other):
        return self.low < other.low < self.high or self.low < other.high < self.high or self.low < other.x < self.high

    def __str__(self):
        return "(x=%d, l=%d)" % (self.x, self.l)


def main():
    n = int(input())
    robots = [Robot(input().split(" ")) for _ in range(n)]
    robots.sort(key=lambda robo: robo.high)
    count = 1
    available = robots[0]
    for i in range(1, n):
        if robots[i].low >= available.high:
            available = robots[i]
            count += 1
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = []
    for _ in range(N):
        x, l = (int(_) for _ in input().split())
        X.append([x-l, x+l])
    X.sort(key=lambda x:x[1])
    output = 0
    last = -10 ** 12
    for i in range(N):
        if last <= X[i][0]:
            output += 1
            last = X[i][1]
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

cur = -float('inf')

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

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
st = []
for i in range(n):
    x, l = map(int, input().split())
    st.append([x-l, x+l])
st.sort(key = itemgetter(1))

i = 1
last = 0
count = 1
while i < n:
    if st[i][0] >= st[last][1]:
        last = i
        count += 1
    i += 1
print(count)

Submission status: Accepted

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

# B - Robot Arms
n = int(input())
robots = []

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

robots.sort(key=lambda x: x[1])
prev_robot = -sys.maxsize
ans = 0

for r in robots:
	if r[0] >= prev_robot:
		ans += 1
		prev_robot = r[1]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
import heapq
q=[]

for i in range(n):
    x,l=map(int,input().split())
    heapq.heappush(q,(x+l,l))

largest=-float('inf')
c=0
while q:
    a,l=heapq.heappop(q)
    if largest<=a-2*l:
        largest=a
        c+=1
print(c)

Submission status: Accepted

Solution code:
n = int(input())

ranges = []

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

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

start = 0
ans = 0
for range in ranges:
    if range[0] >= start:
        start = range[1]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def solve(N, data):
   ret = N
   data.sort(key=lambda x: x[0] - x[1])
   most_right = float("-inf")
   for idx, d in enumerate(data):
       l, r = d[0] - d[1], d[0] + d[1]
       if not idx:
           most_right = r
           continue
       if most_right <= l:
           most_right = r
           continue
       ret -= 1
       most_right = min(r, most_right)
   return ret

if __name__ == "__main__":
    N = int(input())
    data = []

    for _ in range(N):
        data.append(list(map(int, input().split())))
    print(solve(N, data))

Submission status: Accepted

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

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

now = -10**9+10
ans=0
for st, en in st_en:
    if now <= st:
        now = en
        ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def cal(XL):
    N = len(XL)
    XL.sort(key = lambda x:x[0])
    for i in range(N):
        XL[i] = [XL[i][0],XL[i][0]-XL[i][1],XL[i][0]+XL[i][1]]
    OP = [XL[0]]

    for i in range(1,N):
        if OP[len(OP)-1][2] > XL[i][1]:
            if OP[len(OP)-1][2] < XL[i][2]:
                #右方向により腕が伸びている方がより邪魔
                pass
            else:
                OP.pop()
                OP.append(XL[i])
        else:
            OP.append(XL[i])

    return len(OP)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

dis=-float('inf')
for i in range(n):
    if dis<=Arm[i][1]:
        cnt+=1
        dis=Arm[i][0]
print(cnt)

Submission status: Accepted

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

# できるだけ少ないロボットを取り除いて条件を満たすようにしたい
ranges = [[x - l, x + l] for x, l in zip(X, L)]
ranges = sorted(ranges, key=lambda x:x[1])

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

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, x, l))
xl.sort()

count = n
flag = 0
for i in range(n-1):
    if flag == 1: # this machine was removed.
        flag = 0
    else:
        left, right, x, l = xl[i]
    if xl[i+1][0] < right: # overlap
        if xl[i+1][1] <= right: # i includes i+1
            count -= 1 # remove i
        else:
            flag = 1
            count -= 1 # remove i+1

print(count)

Submission status: Accepted

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

width = []
for i in range(N):
  width.append([x[i]-l[i],x[i]+l[i]])

width = sorted(width, key=lambda x: x[1])
res = N
for i in range(1, N):
  if width[i-1][1] > width[i][0]:
    width[i][1] = width[i-1][1]
    res -= 1

print(res)

Submission status: Accepted

Solution code:
n = int(input())
X = []
for i in range(n):
    x, y = map(int, input().split())
    X.append((x - y, x + y))
X.sort(key=lambda x: x[1])
ter = -10**10
cnt = 0
for left, right in X:
    if ter <= left:
        ter = right
        cnt += 1
print(cnt)

Submission status: Accepted

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

T = sorted(K,key=lambda x:x[1])
a = T[0][1]

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

Submission status: Accepted

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

max_r, cnt = -float('inf'), 0
for l, r in robo:
    if  max_r <= l:
        cnt += 1
        max_r = r
print(cnt)

Submission status: Accepted

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

max_r, cnt = -float('inf'), 0
for l, r in robo:
    if  max_r <= l:
        cnt += 1
        max_r = max(max_r, r)
print(cnt)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n = II()
    xl = [MII() for _ in range(n)]
    lr_x = [[x-l, x+l] for x, l in xl]
    lr_x.sort(key=lambda x: x[1])
    now = -(10**9)
    cnt = 0
    for l, r in lr_x:
        if now <= l:
            cnt += 1
            now = r
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

ans = 1
limit = lst[0][1]
for i in range(n):
  if lst[i][0] >= limit:
    ans += 1
    limit = lst[i][1]

print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint


n = int(input())

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

#2次元配列リストのソートでは0番目の要素が比較されるとのこと。
#https://note.nkmk.me/python-list-2d-sort/
#xl.sort()

robot_area = []

for i in range(n):
    startpoint = xl[i][0] - xl[i][1]
    endpoint = xl[i][0] + xl[i][1]
    #この後のsortのことを考えて、endpointを0番目の要素とする。
    robot_area.append([endpoint,startpoint])

robot_area.sort()

counter = 0

#初期値は負の無限大とする。
before_point = -float('inf')

for j in range(n):
    #開始エリアが前回の終了エリアより大きければOK
    if robot_area[j][1] >= before_point:
        counter += 1
        before_point = robot_area[j][0]
    else:
        pass

print(counter)

Submission status: Accepted

Solution code:
def resolve():
	n = int(input())
	robots = [list(map(int, input().split())) for _ in range(n)]
	robots.sort(key=lambda x: x[0] + x[1])
	t = robots[0][0] + robots[0][1]
	a = n
	for i in range(1, n):
		if t <= robots[i][0] - robots[i][1]:
			t = robots[i][0] + robots[i][1]
		else:
			a -= 1
	print(a)
resolve()

Submission status: Accepted

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

d.sort(key=lambda x:x[1])
ma = -9999999
c = 0
for i in range(n):
    if(d[i][0] >= ma):
        ma = d[i][1]
        c += 1
print(c)

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N = II()
    robots = [0]*N
    for i in range(N):
        x, l = map(int,input().split())
        left = x-l
        right = x+l
        robots[i]=(right,left)
    robots.sort()
    dbg(robots)
    prev_right = robots[0][0]

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



    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
m = map(int,read().split())
xl = zip(m,m)
c = [(x-l,x+l) for x,l in xl]
  
from operator import itemgetter
c.sort()
c.sort(key=itemgetter(1))

ans = 1
chk = c[0][1]
for i,j in c:
  if i >= chk:
    ans +=1
    chk = j
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
c = []
for i in range(n):
  l,x = map(int,input().split())
  c.append((l-x,l+x))
  
from operator import itemgetter
c = sorted(c,key=itemgetter(0))
c = sorted(c,key=itemgetter(1))

ans = 1
chk = c[0][1]
for i,j in c:
  if i >= chk:
    ans +=1
    chk = j
    
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])
arm.sort()
dp = [[0,0] for i in range(n)]
dp[0][1] = arm[0][0] + arm[0][1]
for i in range(1,n):
    if dp[i-1][1] <= arm[i][0] -arm[i][1]:
        dp[i][0] = dp[i-1][0]
        dp[i][1] = arm[i][0] + arm[i][1]
    else:
        dp[i][0] = dp[i-1][0] + 1
        dp[i][1] = min(arm[i][0] + arm[i][1],dp[i-1][1])
        
print(n-dp[n-1][0])

Submission status: Accepted

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

def keyence20_b():
    _ = int(readline())
    Robots = []
    for line in readlines():
        # (左端,右端) の形で格納
        x, l = map(int, line.strip().split())
        Robots.append((x-l, x+l))
    # 右端の昇順にソート
    Robots = sorted(Robots, key=lambda x: x[1])

    ans = 0
    x = -10**10  # 使用済み範囲
    for lf, rt in Robots:
        if x <= lf:
            ans += 1  # 他とぶつからないので採用(ゼロタッチは有効)
            x = rt
    print(ans)

keyence20_b()

Submission status: Accepted

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

    ans = 0
    tmp = -1

    for t,s in arms:
        if s >= tmp:
            tmp = t
            ans += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    n = int(input())
    x, l = [0]*n, [0]*n
    for i in range(n):
        x[i], l[i] = map(int, input().split())
    hoge = []
    for i in range(n):
        hoge.append([x[i]+l[i], x[i]-l[i]])
    hoge.sort()
    t = -1000000000000000000000
    ans = 0
    for i in range(n):
        if t <= hoge[i][1]:
            ans += 1
            t = hoge[i][0]
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

cnt = 0
for i in range(n):
    if(i==0):
        last=move[i][1]
        cnt+=1
        continue
    if(move[i][0]<last):
        continue
    last = move[i][1]
    cnt += 1
print(cnt)

Submission status: Accepted

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

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

count = 0
tail = 0

for j in range(N):
    if r_list[j][1] >= tail:
        count += 1
        tail = r_list[j][0]
print(count)

Submission status: Accepted

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

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

ans = 0
st = lst[0][0]
for _ in lst:
    if st <= _[0]:
        st = _[1]
        ans += 1
print(ans)

Submission status: Accepted

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


cnt=0
prev=-float('inf')
for l,r in XL:
    if prev<=l:
        prev=r
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())

s = []
t = []

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

st = sorted([(s[i],t[i]) for i in range(N)], key=itemgetter(1))

ans = 0
last = -10000000

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = [list(map(int,input().split())) for i in range(n)]
    st = sorted([(i[0]-i[1],i[0]+i[1]) for i in x], key=lambda x:(x[1]))
    cnt = 0
    idx = -10**10
    for i in range(n):
        if idx <= st[i][0]:
            cnt += 1
            idx = st[i][1]
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
rng_s = -10**9
for i in rng:
    if rng_s <= i[0]:
        ans += 1
        rng_s = i[1]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N = int(input().strip())
XL = [[int(str) for str in input().strip().split()] for _ in range(N)]


def solve():
    AB = [(x - l, x + l) for x, l in XL]
    AB.sort(key=lambda x: x[1])
    removed = -float('Inf')
    ans = 0
    for a, b in AB:
        if a < removed:
            continue
        removed = b
        ans += 1

    print(ans)


solve()

Submission status: Accepted

Solution code:
N = int(input())
R = [tuple()] * N
for i in range(N):
    x, l = map(int, input().split())
    R[i] = (x-l, x+l)
R = sorted(R, key=lambda x: x[1])
res = 0
prev = -float('inf')
for l, r in R:
    if l >= prev:
        prev = r
        res += 1
print(res)

Submission status: Accepted

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

#print(A)
#now = A[0][0] + A[0][1]
cnt = 0
now = -(1<<60)
for i in range(n):
    f,s = A[i]
    if now > f:
        continue
    cnt += 1
    now = s
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a-b, a+b])
ab = sorted(ab, key=lambda x: x[1])

right_reach = ab[0][1]

count = 0

for i in range(1,n):
    if ab[i][0] < right_reach:
        count += 1
    else:
       right_reach =  ab[i][1]
print(n-count)

Submission status: Accepted

Solution code:
n = int(input())

# 各ロボットの左腕の端(la)と右腕の端(ra)をリストにして入れる
arms = []
for i in range(n):
    x, l = map(int, input().split())
    la = x-l
    if la<0:
        la = 0
    arms.append([la, x+l])

# 右腕の値が小さい順にsort
arms.sort(key=lambda arm: arm[1])

# 残せるロボットの数
robo_n = 0
# 最後に選んだ右腕の座標
ra = 0
for arm in arms:
    # 最後に選んだ右腕の座標より、今の左腕の座標の方が大きいとき値を更新
    if ra <= arm[0]:
        ra = arm[1]
        robo_n += 1

print(robo_n)

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])
ans = 1
r = li[0][1]
for i in range(1,n):
    if r <= li[i][0]:
        ans += 1
        r = li[i][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=sorted(R)
now=-(10**9+1)
minr=-(10**9+1)
count=0
for t in R:
    l,r=t
    if now<=l:
        if l<minr:
            minr=min(r,minr)
        else:
            count+=1
            now=l
            minr=r
    else:
        continue

print(count)

Submission status: Accepted

Solution code:
N = int(input())

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

# 区間の座標に変換
robot_range = []
for i in xl:
    robot_range.append([i[0]+i[1], i[0]-i[1]])

robot_range = sorted(robot_range)

tail = robot_range[0][0]
ans = 1

for rl in robot_range:
    if rl[1] < tail:
        continue
    else:
        ans += 1
        tail = rl[0]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
li = []
for _ in range(n):
    a,b = map(int,input().split())
    li.append([a+b,a-b])
li.sort()
#print(li)
last = 0
count = 0
for i,l in enumerate(li):
    if i == 0:
        last = l[0]
        count += 1
        continue
    #print(l,l[1],last,'last')
    if l[1]>=last:
        count += 1
        last = l[0]
print(count)

Submission status: Accepted

Solution code:
n = int(input())

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

last = -10**10
count = 0
for e, s in t:
    if s >= last:
        last = e
        count += 1

print(count)

Submission status: Accepted

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

cnt = 0
last = -float('inf')
for right, left in robots:
    # 手前のロボットの右手が次のロボットの左手よりも小さいか判定
    if last <= left:
        cnt += 1
        last = right

print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b
n = int(input())
robots = []
for _ in range(n):
    x, l = map(int, input().split())
    a, b = x - l, x + l
    robots.append((a, b))

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

t = 0
pre = robots[0][1]
for i in range(1, n):
    a, b = robots[i]
    if a < pre:
        t += 1
    else:
        pre = b
ans = n - t
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    robots = []
    for i in range(n):
        x, l = map(int, input().split())
        robots.append((x - l, x + l))
    robots = sorted(robots, key=lambda x: x[1])
    ans = []
    for i in range(n):
        if i == 0:
            ans.append(robots[i][1])
        else:
            if robots[i][0] >= ans[-1]:
                ans.append(robots[i][1])
    print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())
W = [[0, 0] for _ in range(N)]

for i in range(N):
    X,L = map(int,input().split())
    W[i][0],W[i][1] = X-L, X+L
W.sort(key=lambda x: x[1])
ans = 0
t = -10**18
for i in range(N):
    if t <= W[i][0]:
        t = W[i][1]
        ans += 1
print(ans)

Submission status: Accepted

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

XL.sort(key=lambda a: (a[0] + a[1], a[0] - a[1]))

ans = 0
R = -10**18
for x, l in XL:
    if R <= x - l:
        ans += 1
        R = x + l
print(ans)

Submission status: Accepted

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

# [終点，始点]のリスト
coordinate = [[i[0] + i[1], max(i[0] - i[1], 0), ] for i in R]
coordinate.sort()

ans = 0
end_point = 0

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xl_=[list(map(int,input().split())) for _ in range(n)]
xl=[[x[0]-x[1],x[0]+x[1]] for x in xl_]
xl.sort(key=lambda x:x[0])
r=xl[0][1]
ans=1
for i in range(1,n):#i-1番目のロボットまでは腕が重ならないことが保証されている。
    if r<=xl[i][0]:
        ans+=1
        r=xl[i][1]
    else:
        r=min(r,xl[i][1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
  x, l = map(int, input().split())
  A[i] = [x + l, x - l]
A.sort()
for i in range(N):
  A[i][0], A[i][1] = A[i][1], A[i][0]
M = A[0][1]
cnt = 1
for i in range(1, N):
  if M <= A[i][0]:
    cnt += 1
    M = A[i][1]
print(cnt)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    n=int(input())
    ST=[]
    for i in range(n):
        x,l=map(int,input().split())
        ST.append((x-l,x+l))
    ST.sort(key=itemgetter(1))
    ans=0
    for i,st in enumerate(ST):
        if i==0:
            ans+=1
            max_t=st[1]
        if max_t<=st[0]:
            ans+=1
            max_t=st[1]
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    n=int(input())
    ST=[]
    for i in range(n):
        x,l=map(int,input().split())
        ST.append((x-l,x+l))
    ST.sort(key=itemgetter(1))
    ans=0
    for i,st in enumerate(ST):
        if i==0:
            ans+=1
            max_t=st[1]
        if max_t<=st[0]:
            ans+=1
            max_t=st[1]
    print(ans)




if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
inf = 10**15
mod = 10**9+7
n = int(input())
rs = [list(map(int, input().split())) for i in range(n)]
rs.sort(key = lambda x : x[0]+x[1])
pre = -inf
ans=0
for i in range(n):
    dis = rs[i][0] - rs[i][1]
    if dis >= pre:
        ans+=1
        pre = rs[i][0] + rs[i][1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
left_list = list()
right_list = list()
for _ in range(N):
    center, length = list(map(int, input().split(' ')))
    left_list.append(center - length)
    right_list.append(center + length)
sorted_robot_list = sorted(range(N), key=lambda i: right_list[i])
robot_cnt = 0
before_robot_right = min(left_list)
for robot in sorted_robot_list:
    current_robot_left = left_list[robot]
    if before_robot_right > current_robot_left:
        continue
    robot_cnt += 1
    before_robot_right = right_list[robot]
print(robot_cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

for i in range(n):
    x = XLs[i][0]
    l = XLs[i][1]
    XLs[i].append(x+l)

#右手の端の位置でソート
XLs.sort(key=itemgetter(2))

choice = -10**10
cnt = 0
for i in range(n):
    x = XLs[i][0]
    l = XLs[i][1]

    if choice <= x-l:
        choice = x+l
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())

X = []
L = []

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

xl = sorted([(X[i],L[i]) for i in range(N)], key = itemgetter(1))

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

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
ans=1
R=[[0]*2 for _ in range(N)]
flag=0
for i in range(N):
    X,L=map(int,input().split())
    R[i][0]=X-L
    R[i][1]=X+L
R.sort(key = lambda x: x[1])
r=R[0][1]
for i in range(1,N):
    if r<=R[i][0]:
        ans+=1
        r=R[i][1]
print(ans)

Submission status: Accepted

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

pre = 0
cnt = 0
for x, l in xl:
    if pre == 0:
        pre = x + l
        continue

    if x - l < pre <= x + l:
        cnt += 1
    elif x + l < pre:
        cnt += 1
        pre = x + l
    else:
        pre = x + l

print(n - cnt)

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.zeros([N, 2])

A[:, 0] = XL[:, 0] - XL[:, 1]
A[:, 1] = XL[:, 0] + XL[:, 1]

A = A[np.argsort(A[:, 1])]

cnt = 0
right = A[0, 0] - 1

for aa in A:
    if right > aa[0]:
        continue
    else:
        cnt += 1
        right = aa[1]

print(cnt)

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]]
t=sorted(t,key=lambda x:x[0]+x[1])
right=t[0][0]+t[0][1]
count=1
for i in range(1,n):
    if t[i][0]-t[i][1]>=right:
        count+=1
        right=t[i][0]+t[i][1]
print(count)

Submission status: Accepted

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

s_t = []
for i in range(N):
    s = X_L[i][0] - X_L[i][1]
    t = X_L[i][0] + X_L[i][1]
    s_t.append([t, s])

s_t.sort()

cnt = 0
t = s_t[0][1]
for i in range(N):
    if t <= s_t[i][1]:
        cnt += 1
        t = s_t[i][0]
print(cnt)