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:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]  
    n = int(input())
    a = []
    for _ in range(n):
        x, l = [int(x) for x in input().split()]  
        s = x - l
        e = x + l
        a.append((s, e))
    a.sort(key=lambda x: x[1])
    ans = 0
    l = float('-inf')
    for s, e in a:
        if s >= l:
            l = e
        else:
            ans += 1
    print(n-ans)

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
a b a
d c d
a b a
"""

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for i in range(n)]
lr = list(map(lambda x:[x[0]-x[1], x[0]+x[1]], xl))
lr.sort(key=lambda x:x[1])
#print(lr)
limit = lr[0][1]
ans=n
for i in range(1, n):
  if lr[i][0]<limit:
    ans-=1
  else:
    limit=lr[i][1]
print(ans)

Submission status: Accepted

Solution code:
import heapq
n=int(input())
rb = []
heapq.heapify(rb)
for i in range(n):
    x,l= map(int,input().split())
    heapq.heappush(rb,(x+l,x-l))
ans=0
mostr=-1
while len(rb)>0:
    c=heapq.heappop(rb)
    if ans==0:
        ans+=1
        mostr=c[0]
    else:
        if mostr<=c[1]:
            ans+=1
            mostr=c[0]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
query = [getList() for i in range(N)]

r_l = []
for x, l in query:
    r_l.append([x - l, x + l])
r_l.sort(key = lambda i:i[1])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    R = []
    for i in range(N):
        x, l = MI()
        R.append((x - l, x + l))
    R = sorted(R, key=lambda x: x[1])
    # print(R)

    rc = -INF
    ans = 0
    for (l, r) in R:
        if rc <= l:
            rc = r
            ans += 1
    print(ans)



if __name__ == '__main__':
    solve()

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()                         #右側で小さい順からソート

def solve() :
    t,ans=-1000000000,0
    for i in range(n) :
        if R[i][1]>=t :
            ans+=1
            t=R[i][0]
    return ans

print(solve())

Submission status: Accepted

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

n = int(input())
robots = [tuple(map(int, input().split())) for _ in range(n)]
robots.sort(key=(lambda robo: robo[0] + robo[1]))

z = -float('inf')
ans = 0
for x, l in robots:
    if z <= x - l:
        ans += 1
        z = x + l

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lst = []
for i in range(n):
    x,l = map(int,input().split())
    if x-l < 0:
        # [右端の位置,左端の位置]
        lst.append([x+l,0])
    else:
        lst.append([x+l,x-l])
lst.sort()


# 最初のロボットの選択
now = lst[0][0]
cnt = 1


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

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
lst = []
for i in range(n):
    x,l = map(int,input().split())
    if x-l < 0:
        # [右端の位置,左端の位置]
        lst.append([x+l,0])
    else:
        lst.append([x+l,x-l])
lst.sort()


# [[6, 0], [7, 1], [12, 6], [105, 95]]

# 最初のロボットの選択
now = lst[0][0]
cnt = 1
idx = 1


for i in range(idx,n):
    if now <= lst[i][1]:
        now = lst[i][0]
        cnt += 1
        idx = i + 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
cou = n
l_h = []
for i in range(n):
  x,l  = map(int,input().split())
  l_h.append([x-l,x+l])
l_h.sort(key=lambda x: x[1])
d = deque(l_h)
t= d.popleft()
a,b = t[0],t[1]
for i in range(n-1):
  m= d.popleft()
  c,e= m[0],m[1]
  if b<=c:
    b = e
  else:
    cou -= 1
print(cou)

Submission status: Accepted

Solution code:
def solve(XL, N):
    XL.sort(key=lambda x:x[1])
    count = N
    for i in range(1, N):
        if XL[i][0] < XL[i-1][1]:
            XL[i][1] = XL[i-1][1]
            count -= 1
    return count
N = int(input())
XL = []
for i in range(N):
    x, l = map(int, input().split(' '))
    XL.append([x-l, x+l])
print(solve(XL, N))

Submission status: Accepted

Solution code:
a=int(input())
b=[list(map(int,input().split())) for i in range(a)]
c=[[i[0]-i[1],i[0]+i[1]] for i in b]
c.sort(key=lambda x: x[1])
ans=0
right=-10**9-1
for i in range(a):
    if right<=c[i][0]:
        ans+=1
        right=c[i][1]
print(ans)

Submission status: Accepted

Solution code:
import copy
import numpy as np
n=int(input())
xl=[]
for i in range(n):
    x,l = map(int,input().split())
    xl.append([x-l,l+x])
#print(xl)
xl = sorted(xl, key=lambda x: x[0],reverse=True)
#print(xl)

ans=0
r=2*(10**9+1)
for i in range(n):
  if xl[i][1]>r:
    continue
  if xl[i][0]<=r:
    r=xl[i][0]
    #print("r",r)
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
rl = [[0, 0]] * n
for i in range(n):
    x, l = map(int, input().split())
    rl[i] = [x + l, x - l]
rl.sort()
l = [0] * n
r = [0] * n
for i in range(n):
    r[i], l[i] = rl[i]
ans = 1
p = 0
for i in range(1, n):
    if r[p] <= l[i]:
        ans += 1
        p = i
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
r = [list(map(int,input().split())) for _ in range(n)]
for i in range(n):
  r[i] = [r[i][0] - r[i][1], r[i][0] + r[i][1]]
r.sort(key = lambda x:x[1])
#print(r)
cur = -1001001001
ans = 0
for i in range(n):
  if cur <= r[i][0]:
    ans += 1
    cur = r[i][1]
print(ans)

Submission status: Accepted

Solution code:
INF = 1 << 60

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

itv = [[x[i] - l[i], x[i] + l[i]] for i in range(n)]
itv.sort(key=lambda x:x[1])
# print("itv =", itv)

ans = 0
t = -INF
for i in range(n):
    if t <= itv[i][0]:
        ans += 1
        t = itv[i][1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = []
for i in range(N):
    x,l = X[i]
    A.append((x-l,x+l))
B1 = sorted(A,key=lambda x:x[1])
B1 = [(B1[i][0],B1[i][1],i) for i in range(N)]
B2 = sorted(B1,key=lambda x:x[0])
hist = [0 for _ in range(N)]
cnt = 0
i = 0
for k in range(N):
    if hist[k]==0:
        r = B1[k][1]
        hist[k] = 1
        cnt += 1
        while i<N:
            l,j = B2[i][0],B2[i][2]
            if hist[j]==1:
                i += 1
                continue
            if l<r:
                hist[j] = 1
                i += 1
            else:
                break
print(cnt)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

from heapq import heappush, heappop
Q = []
for _ in range(N):
    x, l = mapint()
    heappush(Q, (x+l, x-l))

ans = 0
now = -10**20
while Q:
    r, l = heappop(Q)
    if l<now:
        continue
    ans += 1
    now = r

print(ans)

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)
#print(X,L)
Y = []
for i in range(N):
  a = X[i]-L[i];b=X[i]+L[i]
  Y.append([a,b])
#print(Y)
Y.sort(key=lambda x : x[1])
ans = 0
end = - float("inf")
for i in range(N):
  if end > Y[i][0]:
    continue
  ans += 1
  end = Y[i][1]
print(ans)

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])
ans = 0
prev = - 10**9
for x, l in XL:
    if prev <= x - l:
        ans += 1
        prev = x + l

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    lst=[]
    for i in range(n):
        a,b=map(int,input().split())
        lst.append([a-b,a+b])
    lst=sorted(lst,key=lambda x:x[1])
    ans=0
    end=-float("inf")
    for i in lst:
        if i[0]>=end:
            ans+=1
            end=i[1]
    print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from operator import itemgetter

n = readint()
a = []
for i in range(n):
    x,l = readints()
    a.append([x-l,x+l])

a.sort(key = itemgetter(1))

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

    L.sort()

    cnt = 0
    right = -10**9
    for r,l in L:
        if right <= l:
            cnt += 1
            right = r

    print(cnt)

main()

Submission status: Accepted

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

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

cnt = 0
prev_right = -10**9+10
for x, l in XL:
    left = x - l
    right = x + l
    if left >= prev_right:
        cnt += 1
        prev_right = right

print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
XL=[]
for _ in range(N):
    a=list(map(int,input().split()))
    XL.append(a)
XL = sorted(XL, key=lambda x:x[0]+x[1])
#前から順に取っていく
#DP[i]:i番目までのロボットで残せるロボットの最大数
#i番目のロボットがどこまでをカバーしているかを格納する必要がある
DP=[[0,0] for i in range(N)]
DP[0][0]=1#個数
DP[0][1]=XL[0][0]+XL[0][1]#カバーしている距離
for i in range(1,N):
    if XL[i][0]-XL[i][1]>=DP[i-1][1]:
        DP[i][0]=DP[i-1][0]+1
        DP[i][1]=XL[i][0]+XL[i][1]
    else:
        DP[i][0]=DP[i-1][0]
        DP[i][1]=DP[i-1][1]
print(DP[-1][0])

Submission status: Accepted

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

for i in range(N):
    XL[i].append(XL[i][0]+XL[i][1])
XL.sort(key=lambda x: x[2])

tmp = -1 * float('inf')
ans = 0
for X,L,right in XL:
    left = X-L
    if left >= tmp:
        tmp = right
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

input = sys.stdin.readline


def main():
    N = int(input())
    LR = [None] * N
    for i in range(N):
        X, L = map(int, input().split())
        LR[i] = (X - L, X + L)

    LR.sort(key=itemgetter(0))
    ans = N
    cur_R = LR[0][1]
    for L, R in LR[1:]:
        if L < cur_R:
            ans -= 1
            if R < cur_R:
                cur_R = R
        else:
            cur_R = R

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

input = sys.stdin.readline


def main():
    N = int(input())
    LR = [None] * N
    for i in range(N):
        X, L = map(int, input().split())
        LR[i] = (X - L, X + L)

    LR.sort(key=itemgetter(0))
    ans = N
    cur_R = LR[0][1]
    for L, R in LR[1:]:
        if L < cur_R:
            ans -= 1
            cur_R = min(cur_R, R)
        else:
            cur_R = R

    print(ans)


if __name__ == "__main__":
    main()

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()
ans = 0
now = -(10 ** 9 + 1)
for (r, l) in R:
    if now <= l:
        ans += 1
        now = r
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

es.sort()
now = -10**18
idx = 0
ans = 0
while 1:
    if idx==N:
        break
    end, start = es[idx]
    if start>=now:
        now = end
        ans += 1
    idx += 1

print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N=int(input())
    robot=[]
    cnt=0
    last = -1e9
    for _ in range(N):
        x, l = map(int,input().split())
        robot.append((x - l, x+l))
    robot.sort(key=lambda x: x[1])
    for i in range(N):
        if last <=robot[i][0]:
            cnt+=1
            last = robot[i][1]
    print(cnt)

Submission status: Accepted

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

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

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

ans = 0
last = -1e9
for ix in range(0, N):
    if last <=  P[ix][0]:
        ans += 1
        last = P[ix][1]

print(ans)

Submission status: Accepted

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

pos.sort()

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arms = []  # [s, t]のリスト
for _ in range(n):
    x, l = map(int, input().split())
    arms.append([x-l, x+l])
ans = 0
pre_t = -1 * float('inf')
arms.sort(key=lambda arm: arm[1])
for i in range(n):
    s, t = arms[i]
    if s >= pre_t:
        ans += 1
        pre_t = t
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

X.sort(key = lambda x: x[1])
cnt = 1
mx = X[0][1]
for i in range(1,n):
    if mx <= X[i][0]:
        cnt += 1
        mx = X[i][1]
print(cnt)

Submission status: Accepted

Solution code:
import sys

if __name__ == "__main__":
    N = int(input())
    X = []
    for _ in range(N):
        x, l = [int(x) for x in input().split(" ")]
        X.append((x - l, x + l))

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

    count = 0
    max_high = -sys.maxsize
    for low, high in X:
        if max_high <= low:

            count += 1
            max_high = high
    print(count)

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    arms=[]
    for _ in range(n):
        x,l=list(map(int,input().split()))
        arms.append([x,l])
    return n,arms

def main(n,arms):
    count=0
    i=0
    j=i+1
    while(j<n):
        l=arms[i][0]+arms[i][1]
        r=arms[j][0]-arms[j][1]
        if l<=r:
            i=j
            j=i+1
        else:
            if arms[i][1]<=arms[j][1]:
                j=j+1
                count+=1
                print('{}, {}: remove {}'.format(i,j,j))
            else:
                i=j
                j=i+1
                count+=1
                print('{}, {}: remove {}'.format(i,j,i))
    return n-count

def main2(n,arms):
    for arm in arms:
        l=arm[0]-arm[1]
        r=arm[0]+arm[1]
        arm.append(l)
        arm.append(r)
    arms.sort(key=lambda x:x[3])
    count=1
    llim=arms[0][3]
    for i in range(1,n):
        if llim<=arms[i][2]:
            count+=1
            llim=arms[i][3]
    return count

if __name__=='__main__':
    n,arms=readinput()
    ans=main2(n,arms)
    print(ans)

Submission status: Accepted

Solution code:
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=lambda x:x[2]) # 右腕の端の位置でソート

choice = -10**10 # 十分小さく(ロボの左腕の端の座標は最大でも -10*9)
cnt = 0
for i in range(n):
  x = XLs[i][0]
  l = XLs[i][1]
  if choice <= x-l: # 腕がかぶってるか判定
    choice = x+l
    cnt+=1 # 被っていなければ残す = カウント+1
print(cnt)

Submission status: Accepted

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

count = 1
i = 1
cur= intervals[0]
while(i < len(intervals)):
	while(i < len(intervals) and cur[1] > intervals[i][0]): i += 1
	if i < len(intervals):
		cur = intervals[i]
		count +=1


print count

Submission status: Accepted

Solution code:
from operator import itemgetter

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

for i in range(N):
    a_temp = XL[i][0] - XL[i][1]
    b_temp = XL[i][0] + XL[i][1]
    a.append(a_temp)
    b.append(b_temp)

XL = sorted([(a[i], b[i]) for i in range(N)], key=itemgetter(1))

ans = 1
last = XL[0][1]

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
(n, ), *r = [[*map(int, i.split())] for i in open(0)]
s = sorted([[x + l, x - l] for x, l in r])
c = 1
p = s[0][0]
for i in s[1:]:
    if i[1] >= p:
        c += 1
        p = i[0]
print(c)

Submission status: Accepted

Solution code:
n = int(input())
lr = [] # 各アームの左端と右端の位置のペア
for _ in range(n):
    x, l = list(map(int, input().split()))
    lr.append((x-l, x+l))

# 右端位置でソート
lr.sort(key=lambda x:x[1])

ans = 0
right = -10**9
for l,r in lr:
    # 重なってないなら残す
    if l >= right:
        ans += 1
        right = r

print(ans)

Submission status: Accepted

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

N = int(readline())
XL = map(int, read().split())
 
LR = sorted(
    [(x - l, x + l) for x, l in zip(XL, XL)],
    key=lambda x: x[1])
LR = [(-3 * 10 ** 9, -3 * 10 ** 9)] + LR
 

i = 1
while True:
    if len(LR) <= i:
        break
 
    _, pr = LR[i - 1]
    cl, cr = LR[i]
 
    if pr <= cl:
        i += 1
    else:
        del LR[i]

print(len(LR) - 1)

Submission status: Accepted

Solution code:
def resolve():
    """
    典型的な区間スケジューリング問題
    各スケジュールの終了時間が短いものから選択していけば，
    選択するスケジュール数が最大になる．
    今回は腕の可動範囲上限の小さいものから選択していく．
    """
    import sys
    
    readline = sys.stdin.readline

    N = int(readline())
    XL = [list(map(int, readline().split())) for _ in [0] * N]

    # 腕の可動範囲の(上限, 下限)のリスト生成
    t = [(x + length, x - length) for x, length in XL]
    
    # 複数要素を含む要素のsortではインデックスの小さい要素から比較していきソート
    t.sort()               # リストを腕の上限の昇順(小さい順)でソート
    time = -float('inf')   # time=0でもおｋ
    ans = 0
    for i in range(N):
        end, start = t[i]  # tはソート済故，上限が小さい順に選出される
        if time <= start:  # 腕の下限が既存の腕と重ならないか判定
            ans += 1
            time = end     # 現在の腕の上限を記録
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

INF = 10**9 + 7


def main():
    N = in_n()
    arms = [tuple()] * N

    for i in range(N):
        x, l = in_nn()
        arms[i] = (x - l, x + l)

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

    r_max = -INF
    count = 0
    for i in range(N):
        l, r = arms[i]
        if r_max <= l:
            r_max = r
            count += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')
n = I()
# 区間スケジューリング問題 : いくつかの区間の中から重ならないように最大で何個選べるか
# ソート + 貪欲法 で解ける
arm_pos = []
for _ in range(n):
    x, l = LI()
    arm_pos.append([x - l, x + l])
arm_pos = sorted(arm_pos, key=lambda x: x[1])  # アームの終点の位置でソート
ans = n
for i in range(n - 1):
    if arm_pos[i][1] > arm_pos[i + 1][0]:  # i のアームの終点が i + 1 のアームの始点 と重なっていた場合
        arm_pos[i + 1] = arm_pos[i]  # i + 1 のアームを取り除く
        ans -= 1
print(ans)

Submission status: Accepted

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

rl=[]
for x,l in xl:
    right=x-l
    left=x+l
    rl.append([right,left])
rl.sort(key=lambda x: x[1])
# print(rl)

cnt=0
pos=-float('inf')
for i in range(n):
    if rl[i][0]>=pos:
        pos=rl[i][1]
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
rom = []
for _ in range(n):
    x, l = map(int, input().split())
    rom.append([x + l, x - l])
    
rom.sort()
ans = 0
pos = -10 ** 10
for end, start in rom:
    if start >= pos:
        ans += 1
        pos = end
print(ans)

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 = sorted(A, key=lambda x:x[1])
now = -10**10
cnt = 0
for x in A:
    if now <= x[0]:
        now = x[1]
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
XL = []
for _ in range(n):
    x, l = map(int, input().split())
    XL.append([x-l, x+l])
XL.sort(key=itemgetter(1))
INF = 10**18
cur = -INF
ans = 0
for i in range(n):
    if cur <= XL[i][0]:
        ans += 1
        cur = XL[i][1]
print(ans)

Submission status: Accepted

Solution code:
#pdf見た
n = int(input())
xl = [list(map(int,input().split())) for i in range(n)]
sf = []
choice = -1e+9
for x,l in xl:
    sf.append([x-l,x+l])
sf.sort(key=lambda x:x[1])
cnt = 0
for s,f in sf:
    if choice <= s:
        cnt += 1
        choice = f
        
print(cnt)

Submission status: Accepted

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

ans = 1
ne = arms[0][1]
for i in range(n):
    if arms[i][0] >= ne:
        ne = arms[i][1]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
x = []

for _ in range(N):
    X, L = MAP()
    x.append([X-L, X+L])

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

ans = 0
tmp = -INF
for l, r in x:
    if tmp <= l:
        tmp = r
        ans += 1
   

print(ans)

Submission status: Accepted

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

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

res = 0
max_r = float("-inf")

sorted_lr = sorted(lr, key=lambda x:x[1])
for lr in sorted_lr:
    if max_r <= lr[0]:
        res += 1
        max_r = lr[1]

print(res)

Submission status: Accepted

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

a = sorted(a, reverse=False, key=lambda x: x[1]) 
tmp = a[0][1]
ans = 1
for i in range(1,len(a)):
    if tmp <= a[i][0]:
        tmp = a[i][1]
        ans += 1 

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(2)] for i in range(N)]

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


T=sorted(S,key=lambda x:x[1])
#U=sorted(T,key=lambda x:x[1])
if N==1:
    print(1)
    exit()


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

Submission status: Accepted

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

'''

区間スケジューリング問題：終点でソートして貪欲法

'''


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 = (始点、終点)

schedule = sorted(schedule, key=lambda x: x[1])
ans = 0
end = -10**12                                   # 始点の最小値

for i in range(N):
    if end <= schedule[i][0]:
        end = schedule[i][1]                    # 終点でソートされているので、自動的に可能な中で最速の終点が選ばれている
        ans += 1

print(ans)

Submission status: Accepted

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

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = II()

    xl = []
    for _ in range(N):
        X, L = MII()
        xl.append((X, L))
    
    xl = sorted(xl, key=lambda x: x[0])

    ans = 1
    r = xl[0][0] + xl[0][1]
    for x, l in xl[1:]:
        if r <= x - l:
            r = x + l
            ans += 1
        elif x + l <= r:
            r = x + l
       
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
r=[]
for _ in range(n):
    s,t=map(int,input().split())

    r.append([s-t,s+t])

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


ans=[r[0]]
for i in range(1,n):
    if r[i][0]>=ans[-1][1]:
        ans.append(r[i])

        


print(len(ans))

Submission status: Accepted

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

#print(robot)

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

Submission status: Accepted

Solution code:
n=int(input())
B=[]
for i in range(n):
  x,l=map(int,input().split())
  B.append([x-l,x+l])
B.sort(key=lambda x:x[1])
max_l=-10**18-5
ans=0
for b in B:
  if max_l <= b[0]:
    max_l = b[1]
    ans+=1
print(ans)