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:
def solve():
    N = int(input())
    XLs = [list(map(int, input().split())) for _ in range(N)]
    XLs.sort(key = lambda x:(x[0],-1*x[1]))
    interval = (XLs[0][0]-XLs[0][1],XLs[0][0]+XLs[0][1])
    ret = 0
    for XL in XLs[1:]:
        interval_ = (XL[0]-XL[1], XL[0]+XL[1])
        if interval_[0] < interval[1]:
            interval = (max(interval[0], interval_[0]),min(interval[1], interval_[1]))
            ret += 1
        else:
            interval = interval_
            
    print(N-ret)
    
solve()

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
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())

ans = 0
p = [[x[i] - l[i], x[i] + l[i]] for i in range(n)]
p.sort(key=lambda a : a[1])
# print(p)
y = -INF
for i in p:
    if i[0] >= y:
        ans += 1
        y = i[1]
print(ans)

Submission status: Accepted

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


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

  X_L.sort(key=lambda x: x[0]+x[1])
  # print(X_L)

  def min_robots(X_L):
    # print(X_L)
    N = len(X_L)
    added = [0]
    for i in range(1, N):
      pre = added[-1]
      if X_L[pre][0] + X_L[pre][1] <= X_L[i][0] - X_L[i][1]:
        added.append(i)
    return len(added)

  print(min_robots(X_L))


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
n = int(input())
L = []
for _ in range(n):
    x, l = map(int, input().split())
    left = x - l
    right = x + l
    L.append((left, right))
L = sorted(L, key=lambda x: x[1])
ans = 0
prev = -float('inf')
for r in L:
    if r[0] >= prev:
        ans += 1
        prev = r[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,2*l])
xl.sort()
r=-10**9
ans=0

for i in range(N):
    if xl[i][0]-xl[i][1]>=r:
        ans+=1
        r=xl[i][0]

print(ans)

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:
n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int,input().split())))

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

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

b = -100000000000000000
c = 0


for i in range(n):
    if d[i][0] >= b:
        b = d[i][1]
        c = c + 1

print(c)

Submission status: Accepted

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

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

d = sorted(d, key = lambda x: x[1])
#print(d)

b = [-100000000000000000]
c = [0]


for i in range(n):
    for j in range(len(b)):
        if d[i][0] >= b[j]:
            b = [d[i][1]]
            c = [c[j] + 1]
            break

    
    #print(b)
    #print(c)

print(max(c))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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=lambda x: x[1])
ans = 0
c = -10**10
for l,r in lr:
    if c<=l:
        ans += 1
        c = r
print(ans)

Submission status: Accepted

Solution code:
def solve(n, x, l):
    p = sorted([(a+b, a-b) for a, b in zip(x, l)])
    _, th = p[0]
    best = 0
    for t, s in p:
        if th <= s:
            best += 1
            th = t
    return best

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

Submission status: Accepted

Solution code:
n=int(input())
st=[]
for i in range(n):
    x,l=map(int,input().split())
    st.append([x-l,x+l])
st.sort(key=lambda x:x[1])
now,ans=0,0
while now<n:
    t=st[now][1]
    while True:
        now+=1
        if now==n: break
        if st[now][0]>=t: break
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
s = []
for i in range(n):
    l = list(map(int, input().split()))
    rang = [l[0] - l[1], l[0] + l[1]]
    s.append(rang)
s_sort = sorted(s, key=itemgetter(1))
ans = 0
last = -float("inf")
for i in range(n):
    if last <= s_sort[i][0]:
        ans += 1
        last = s_sort[i][1]
print(ans)

Submission status: Accepted

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

last_right = arms[0][1]
ans = 1
for i in range(1, n):
    left, right = arms[i]
    if left < last_right:
        continue
    last_right = right
    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])
XL.sort(key=lambda x: x[1])

res = 0
now = -10 ** 9
for s, e in XL:
    if now <= s:
        now = e
        res += 1

print(res)

Submission status: Accepted

Solution code:
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10 ** 9 + 7
def solve():
    n = getN()
    arms = []
    for i in range(n):
        x, l = getList()
        arms.append((x-l, x+l))

    arms.sort()
    # print(arms)
    prev = -INF
    ans = n
    for arm in arms:
        if arm[0] < prev:
            ans -= 1
            if arm[1] <= prev:
                prev = arm[1]
        else:
            prev = arm[1]

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = ILL(N)

B = [[x-y,x+y] for x,y in A]
B = sorted(B,key = lambda x:x[1])
r = -INF
ans = 0
for x,y in B:
  if x>=r:
    ans += 1
    r = y
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

tmp=-10**10
ans=0
for i in range(N):
    end,start=robot[i]
    if tmp<=start:
        tmp=end
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = []
    for _ in range(n):
        x, l = map(int, input().split())
        X.append([x - l, x + l])
    X = sorted(X, key=lambda x: x[1])

    remove = 0
    prev = X[0][1]
    for i in range(1, n):
        if X[i][0] < prev:
            remove += 1
        else:
            prev = X[i][1]
    print(n - remove)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

INF = 10**18
X = -INF
ans = 0
for L, R in coordinates:
    if L < X:
        continue
    X = R
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter
INF = 10 ** 10

def main():
    N = int(readline())
    L = []
    for _ in range(N):
        x, l = map(int, readline().rstrip().split())
        L.append([x - l, x + l])

    L.sort(key=itemgetter(1))
    cur = -INF
    res = 0

    for left, right in L:
        if left >= cur:
            res += 1
            cur = right
    
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = [0]*n
for i in range(n):
    x[i] = list(map(int,input().split()))
x.sort(key= lambda val : val[0])
i = 0
while 1:
    if i >= n - 1:
        break
    
    if x[i][0] + x[i][1] > x[i+1][0] - x[i+1][1]:
        if x[i][0] + x[i][1] > x[i+1][0] + x[i+1][1]:
            del x[i]
            n -= 1
        else:
            del x[i+1]
            n -= 1
    else:
        i += 1
print(len(x))

Submission status: Accepted

Solution code:
N, *XL = map(int, open(0).read().split())
XL = sorted((x + l, x - l) for x, l in zip(*[iter(XL)] * 2))
curr = -float("inf")
ans = 0
for right, left in XL:
    if left >= curr:
        curr = right
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
(N,), *XL = [list(map(int, s.split())) for s in open(0)]
XL.sort(key=lambda x: x[0] + x[1])
curr = -float("inf")
ans = 0
for x, l in XL:
    if x - l >= curr:
        curr = x + l
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
itv = []
for i in range(n):
    x,l = map(int, input().split())
    start = x - l if x - l > 0 else 0
    end = x + l
    itv.append([end, start])

itv.sort()

ans, t = 0, 0
for [x, l] in itv:
    if t <= l:
        ans += 1
        t = x

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as lower_bound
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    XL = []
    ans = 0

    for i in range(N):
        x, l = MI()
        XL.append((x + l, x - l))

    # print(XL)
    XL.sort()

    cur = -10**19
    r = 0

    for i in range(N):
        if XL[i][1] >= cur:
            r += 1
            cur = XL[i][0]
        # print(i, cur)

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
List=[]
for i in range(a):
  u,v=mi()
  List.append([u-v,u+v])
List=sorted(List , key=lambda x:x[1])
q=deque([List[0][1]])
ans=1
for i,j in List:
  u=q.pop()
  if u<=i:
    q.append(j)
    ans+=1
  else:
    q.append(u)
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))
lr.sort(key=lambda x: x[1])
ans=0
l=-10**18
r=0
for i in range(n):
  if i==0:
    tl,tr=lr[i]
    l=tl
    r=tr
    ans+=1
    continue
  tl,tr=lr[i]
  if tl>=r:
    ans+=1
    r=tr
    l=tl
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xlr=[[] for _ in range(n)]

for i in range(n):
    xx,ll = map(int,input().split())
    xlr[i] = [xx,ll,xx-ll,xx+ll]
    
xlr.sort(key = lambda x:x[3])

ans=1
right=xlr[0][-1]
for i in range(1,n):
    if right <= xlr[i][2]:
        ans+=1
        right=xlr[i][-1]

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n=int(input())
s=[""]*n
t=[""]*n
for i in range(n):
    x,l=map(int,input().split())
    s[i]=x-l
    t[i]=x+l
st=sorted([(s[i],t[i]) for i in range(n)], key=itemgetter(1))
ans=0
last=0
last=-float("inf")
for i in range(n):
    if last<=st[i][0]:
        ans+=1
        last=st[i][1]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
import bisect
L=[]
for i in range(n):
    x,l=map(int,input().split())
    a=x-l+0.1
    b=x+l-0.1
    L.append((b,a))
L=sorted(L)
rob=1
bottom=L[0][0]
for i in range(1,n):
    if L[i][1]>bottom:
        rob += 1
        bottom=L[i][0]
print(rob)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
    x,y = map(int, input().split())
    A.append([x+y,x-y])
A.sort()
now = -float('inf')
ans = 0
for a,b in A:
    if b>=now:
        ans += 1
        now = a
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


from queue import PriorityQueue


def main():
    n = gete(int)
    que = PriorityQueue()

    for _ in range(n):
        x, l = geta(int)
        que.put((x + l, x - l))

    ans = 0
    max_r = -10**9

    while not que.empty():
        r, l = que.get()

        if max_r <= l:
            max_r = r
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from operator import itemgetter
def main():
    n = int(input())
    robots = []
    for _ in range(n):
        x, l = map(int, input().split())
        lside = x - l
        rside = x + l
        robots.append((lside, rside))
    # ロボットの腕の右端を基準にして昇順ソート。
    robots = sorted(robots, key=itemgetter(1))
    robots = deque(robots)
    a_robot = robots.popleft()
    cnt = n
    while robots:
        robot_next = robots.popleft()
        if a_robot[1] > robot_next[0]:
            cnt -= 1
        else:
            a_robot = robot_next
            continue
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
A = []
for x, l in XL:
    A.append([x + l, x - l])
A.sort()
B = []
i = 0
while True:
    B.append(A[i])
    if i == N - 1:
        break
    j = 1
    while True:
        if A[i][0] > A[i + j][1]:
            j += 1
            if i + j == N:
                break
            continue
        else:
            break
    if i + j == N:
        break
    i = i + j
print(len(B))

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N = int(input())
    robots = [[int(item) for item in input().split()] for _ in range(N)]


    arm_body_arm = []

    for body, arm in robots:
        arm_body_arm.append([body - arm, body + arm])
    
    arm_body_arm = sorted(arm_body_arm, key=lambda x:x[1])

    res = 1
    prev = arm_body_arm[0][1]
    for start, end in arm_body_arm:
        if prev <= start:
            res += 1
            prev = end

    print(res)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

Submission status: Accepted

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


def read():
    N = int(input().strip())
    XL = []
    for i in range(N):
        x, l = map(int, input().strip().split())
        XL.append((x, l))
    return N, XL


def solve(N, XL):
    XL.sort(key=lambda x: x[0]+x[1])
    r = -10**9-1
    count = 0
    for x, l in XL:
        if r <= x - l:
            r = x + l
            count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
def main():
    N, *XL = map(int, open(0).read().split())
    # print(N, XL)
    robots = [0]*N
    for i in range(N):
        X, L = XL[2 * i + 0], XL[2 * i + 1]
        robots[i] = (X - L, X + L)
    robots.sort(key=lambda x: x[1])
    # print(robots)
    ans = 0
    last = robots[0][0] - 1
    for robot in robots:
        if last <= robot[0]:
            last = robot[1]
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
sec = []

for _ in range(N):
    x, l = map(int, sys.stdin.readline().rstrip().split())
    sec.append((x - l + 1, x + l - 1))

sec = sorted(sec, key=lambda x: x[1])
r = -10**10
ans = 0
for s, t in sec:
    if r + 1 < s:
        ans += 1
        r = t
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
sec = []

for _ in range(N):
    x, l = map(int, sys.stdin.readline().rstrip().split())
    sec.append((x - l, x + l))

sec = sorted(sec, key=lambda x: x[1])
r = -float("inf")
ans = 0
for s, t in sec:
    if r <= s:
        ans += 1
        r = t
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
sec = []

for _ in range(N):
    x, l = map(int, sys.stdin.readline().rstrip().split())
    sec.append((x - l, x + l))

sec = sorted(sec, key=lambda x: x[1])
r = -10**10
ans = 0
for s, t in sec:
    if r <= s:
        ans += 1
        r = t
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L = []
for _ in range(n):
    x, l = map(int, input().split())
    L.append([x - l, x + l])
L = sorted(L, key=lambda x: x[1])
ans = 0
r = -float('inf')
for i in range(n):
    if L[i][0] >= r:
        ans += 1
        r = L[i][1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

P = []
for _ in range(N):
  x,l = list(map(int, input().split()))
  P.append((x+l, x-l))
  
P.sort()
rw = P[0][0]
ans = 1
for i in range(1,N):
  r,l = P[i]
  if l < rw:
    continue
  else:
    rw = r
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xl = []
for i in range(n):
    l, r = map(int, input().split())
    xl.append([l-r, l+r])
xl.sort(key=lambda x: x[1])
ans = 0
inf = 10 ** 10
prev_r = - inf
for l, r in xl:
    if prev_r > l:
        continue
    ans += 1
    prev_r = r
print(ans)

Submission status: Accepted

Solution code:

N = int(input())
L = []

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

L = sorted(L, key = lambda x:x[1])
start = L[0][1]
ans = 1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
list=[0 for i in range(N)]
for  i in range(N):
 x,l=map(int,input().split())
 list[i]=[x-l,x+l]
list.sort(key=lambda x: x[1])
ans=0
haji=-(10**10)
for  i in range(N):
 if list[i][0]>=haji:
  ans+=1
  haji=list[i][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    # 区間スケジューリングの典型問題
    # 選べる中で最小の終点を選んでいく
    N = int(input())
    sec = [[0,0] for _ in range(N)]
    for i in range(N):
        X,L = map(int, input().split())
        sec[i][0] = X+L
        sec[i][1] = X-L
    # 終点で昇順ソート
    sec = sorted(sec)
    ans = 1
    now = sec[0][0]
    for i in range(1,N):
        if sec[i][1]>=now:
            # 残す
            ans += 1
            now = sec[i][0]
    print(ans)

main()

Submission status: Accepted

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

from operator import itemgetter

# 区間スケジューリング

N = int(readline())
m = map(int,read().split())
XL = zip(m,m)

LR = [(x-l,x+l) for x,l in XL]
LR.sort(key = itemgetter(1))

INF = 10 ** 18
prev_R = -INF
cnt = 0
for L,R in LR:
    if prev_R > L:
        continue
    cnt += 1
    prev_R = R

print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
arms = []
finishtime = float('-inf')
for i in range(N):
    x,l = map(int,input().split())
    arms.append((x-l,x+l))
arms.sort(key=itemgetter(1))
cnt=0
for L,R in arms:
    if finishtime<=L:
        cnt+=1
        finishtime = R
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
arms = []
finishtime = float('-inf')
ans=[]
for i in range(N):
    x,l = map(int,input().split())
    arms.append((x-l,x+l))
arms.sort(key=itemgetter(1))
for i in range(N):
    if arms[i][0]>=finishtime:
        ans.append(i)
        finishtime = arms[i][1]
print(len(ans))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
X = [[] for _ in range(N)]
L = [[] for _ in range(N)]

for i in range(N):
    X[i], L[i] = map(int, input().split())
    
    
def indexSort(L):
    D = dict(zip(range(len(L)), L))
    E = sorted(D.items(), key=lambda x: x[1])
    F = [e[0] for e in E]
    return F

L1 = [x-l for x, l in zip(X, L)]
L2 = [x+l for x, l in zip(X, L)]


Ind = np.argsort(L2)

Remain = [Ind[0]]
i = 0
while i < len(Ind)-1:
    now = Remain[-1]
    After = Ind[i+1:]

    skip = 0
    for after in After:
        if L2[now] > L1[after]:
#            print(L2[now], L1[after])
            skip += 1
        else:
#            print(after)
            Remain.append(after)
            break
    i += 1 + skip  
print(len(Remain))

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()
max_r = -float('inf')
ans = 0
for i in range(n):
    if max_r<=t[i][1]:
        ans+=1
        max_r=t[i][0]
print(ans)

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 r,l in robots:
    if last <= l:
        cnt += 1
        last = r
 
print(cnt)

Submission status: Accepted

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

N = int(input().strip())
XL_list = [list(map(int, input().rstrip().split())) for i in range(N)]
#-----

section = []

for X,L in XL_list:
    section.append( ( X - L , X + L ) )


section.sort(key= lambda x: x[1])
prev_tail = -float("inf")
cnt = 0

for left,right in section:
    if prev_tail <= left:
        cnt += 1
        prev_tail = right
        

print(cnt)