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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, X: "List[int]", L: "List[int]"):
    # 昇順に考えて良い
    X, L = zip(*sorted(zip(X, L)))

    # i番目とi+1番目が重なる場合にTrue
    overlay = [0]*(N-1)
    for i in range(N-1):
        overlay[i] = X[i+1]-L[i+1] < X[i]+L[i]

    past = False
    count = 0
    for i in range(N-1):
        if overlay[i] == False:
            past = False
        elif past == False:
            past = True
        else:
            count += 1
            past = False
    if past == True:
        count += 1
    print(N-count)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
robots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

x_max = -10**10
ans = 0
for x, l in robots:
    if x - l >= x_max:
        ans += 1
        x_max = x + l
print(ans)

Submission status: Wrong Answer

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

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

count = 0
pos = -10000000000

for elem in robot:
    if elem[0] >= pos + elem[1]:
        count += 1
        pos = elem[0] + elem[1]

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
rm = 0
r = -float('inf')
robot = sorted([list(map(int, input().split())) for i in range(N)])
for x, l in robot:
    if x - l < r:
        rm += 1
    else:
        r = x + l

print(N - rm)

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
ans = 0
prex = -1 * 10**9
data.sort()
for i in range(n):
    x, l = data[i]
    if prex <= x - l:
        prex = x + l
    else:
        ans += 1
print(n-ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
a.sort()
a.append([10**9+1,0])
ans = 0
left = [a[0]]
for i in range(1,n):
  if a[i][0]-a[i][1] >= left[-1][0]+a[-1][1]:
    left.append(a[i-1])
print(len(left))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

robos.sort()

kosuu = 0
maenomigi = -100000000000000000000000
for x, l in robos:
    # ok
    if maenomigi <= x - l:
        maenomigi = x + l
        kosuu += 1

print(kosuu)

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
for i in range(n):
    a, b = map(int, input().split())
    data.append([a-b, a+b])

data = sorted(data)
end = -1000000000000
ans = 0
for i in data:
    if(i[0] >= end):
        ans+=1
        end = i[1]

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

xl = [tuple(map(int, input().split())) for _ in range(n)]
xl = sorted(xl)
res = 1
x, l = xl[0]
cur = x + l
for (x, l) in xl:
    if x - l >= cur:
        cur = x + l
        res += 1
print(res)

Submission status: Wrong Answer

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

XL = [(X[i], L[i]) for i in range(N)]
XL.sort()
for i in range(N):
  X[i], L[i] = XL[i]

ans = N
m = -10**20
for i in range(N):
  if X[i]-L[i]<m:
    ans -= 1
  else:
    m = max(m, X[i]+L[i])
print ans

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in [0] * n]

s = sorted(s, key=lambda x: x[0])

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

print(n)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N=int(input())
xl=[list(map(int, input().split())) for i in range(N)]
xl=sorted(xl, key=itemgetter(0))

hiku=0
i=1
while i<N:
  if xl[i-1][0]+xl[i-1][1]>xl[i][0]-xl[i][1]:
    hiku+=1
    i+=2
  else:
    i+=1
    
print(N-hiku)

Submission status: Wrong Answer

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

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

for i in range(n):
    A.append([L[i][0]-L[i][1], L[i][0]+L[i][1]])
A.sort()

m = -float("inf")
ans = 0
for i in range(n):
    if m > A[i][0]:
        ans += 1
    else:
        m = A[i][1]
print(n-ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    p.sort(key = lambda x:x[0]+x[1])
    t = p[0][0]+p[0][1]
    ans = 1
    for x, l in p[1:]:
        if x < t:
            continue
        t = x+l
        ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=0
xxx=[list(map(int,input().split()))for _ in range(n)]
xxx.sort()
x,l=xxx[0]
for i in range(1,n):
  xx,ll=xxx[i]
  if x+l>xx-ll:ans+=1
  else:x,l=xx,ll
print(n-ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    p.sort()
    t = p[0][0]+p[0][1]
    ans = 1
    for x, l in p[1:]:
        if x < t:
            continue
        t = x+l
        ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math , sys
N = int( input() )

X = []
for i in range(N):
    A , B = list(map(int, input().split()))
    X.append([i , A-B , A , A+B])


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

Y = X.pop(0)
Ri = Y[-1]
ans = 1

j=0

while len(X)>0:
    Y = X.pop(0)
    if Y[1]>=Ri:
        ans+=1
        Ri = Y[-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
se = [()] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = (x-l, x+l)
se = sorted(se, key=lambda x: x[1])
ans = []
while se:
	now = se.pop(0)
	temp = []
	for i, s in enumerate(se):
		if now[1] <= s[0]:
			temp = se[i:]
			break
	se = temp
	ans.append(now)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
se = [()] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = (x-l, x+l)
se = sorted(se, key=lambda x: x[1])
ans = []
while se:
	now = se.pop(0)
	temp = []
	for s, e in se:
		if now[1] <= s:
			temp.append((s, e))
	se = temp
	ans.append(now)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
se = [()] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = (x-l, x+l)
se = sorted(se, key=lambda x: x[1])
while True:
	ef = True
	for i, (_, e) in enumerate(se[:-1]):
		if e > se[i+1][0]:
			se.remove(se[i+1])
			ef = False
			break
	if ef:
		break
print(len(se))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = []
for _ in range(N):
  x, l = map(int, input().split())
  L.append([x-l, x+l])
L.sort(key=lambda x: x[1])
s, ans = -10**8, 0
while True:
  for l in L:
    if s<=l[0]:
      ans += 1
      s = l[1]
      break
  else:
    break
print(ans)

Submission status: Time Limit Exceeded

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

for i in a[1:]:
    for j, k in enumerate(b):
        if not (k[1] <= i[0]):
            break
        if j == len(b)-1:
            ans += 1
            b.append(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import numpy as np
p = []
if __name__ == '__main__':
    N = int(input())
    X = [0]*N
    L = [0]*N
    for i in range(N):
        X[i], L[i] = map(int, input().split())
        p.append([X[i] - L[i], X[i] + L[i]])
        n_p = np.array(p)
        col_num = 1
        sort_n_p = n_p[np.argsort(n_p[:, col_num])]
    counter = 0
    t = -10000
    for i in range(N):
        if t <= sort_n_p[i][0]:
            counter += 1
            t = sort_n_p[i][1]

    print(counter)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
p = []
if __name__ == '__main__':
    N = int(input())
    X = [0]*N
    L = [0]*N
    for i in range(N):
        X[i], L[i] = map(int, input().split())
        p.append([X[i] - L[i], X[i] + L[i]])
        p.sort(key = itemgetter(1))
    counter = 0
    t = -10000
    for i in range(N):
        if t <= p[i][0]:
            counter += 1
            t = p[i][1]

    print(counter)

Submission status: Time Limit Exceeded

Solution code:
p = []
if __name__ == '__main__':
    N = int(input())
    X = [0]*N
    L = [0]*N
    for i in range(N):
        X[i], L[i] = map(int, input().split())
        p.append([X[i] - L[i], X[i] + L[i]])
        p.sort(key = lambda x: x[1])
    counter = 0
    t = -10000
    for i in range(N):
        if t <= p[i][0]:
            counter += 1
            t = p[i][1]

    print(counter)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
n=int(input())
xl=[list(map(int,input().split()))  for i in  range(n)]

cp=copy.deepcopy(xl)
cp=np.array(cp)
cp=cp.T
#xSort = np.sort(cp[0])[::-1]
dict={k: v for v, k in enumerate(cp[0])}
xr=[x+cp[1][dict[x]] for x in cp[0]]
xl=[x-cp[1][dict[x]] for x in cp[0]]
#print(xr)
#print(xl)
xlc=copy.deepcopy(xl)
xl.sort(reverse=True)
xrs=[xr[xlc.index(x)] for x in xl]
#print("xrs", xrs)
#print("xls", xls)

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
n=int(input())
xl=[list(map(int,input().split()))  for i in  range(n)]

cp=copy.deepcopy(xl)
cp=np.array(cp)
cp=cp.T
#xSort = np.sort(cp[0])[::-1]
dict={k: v for v, k in enumerate(cp[0])}
xr=[x+cp[1][dict[x]] for x in cp[0]]
xl=[x-cp[1][dict[x]] for x in cp[0]]
#print(xr)
#print(xl)
xls=sorted(xl, reverse=True)
xrs=[xr[xl.index(x)] for x in xls]
#print("xrs", xrs)
#print("xls", xls)

ans=0
r=10**5+1
for i in range(len(xls)):
  if xrs[i]>r:
    continue
  if xls[i]<=r:
    r=xls[i]
    #print("r",r)
    ans+=1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
n=int(input())
xl=[list(map(int,input().split()))  for i in  range(n)]

cp=copy.deepcopy(xl)
cp=np.array(cp)
cp=cp.T
xSort = np.sort(cp[0])[::-1]
dict={k: v for v, k in enumerate(cp[0])}

xr=[x+cp[1][dict[x]] for x in xSort]
xl=[x-cp[1][dict[x]] for x in xSort]
#print(xr)
#print(xl)
xls=sorted(xl, reverse=True)
xrs=[xr[xl.index(x)] for x in xls]
#print("xrs", xrs)
#print("xls", xls)

ans=0
r=10**5+1
for i in range(len(xls)):
  if xrs[i]>r:
    continue
  if xls[i]<=r:
    r=xls[i]
    #print("r",r)
    ans+=1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
start = [0] * N
end = [0] * N
imosu = [0] * (2 * N)
imosu2 = [-10 ** 10] * (2 * N)
imosu3 = [0] * (2 * N)
for i in range(N):
  x, l = map(int, input().split())
  start[i] = x - l
  end[i] = x + l
  imosu[2 * i] = x - l
  imosu[2 * i + 1] = x + l
imosu = sorted(imosu)
#print(start, end, imosu)
j = 0
for i in range(2 * N):
  if i == 0:
    imosu2[j] = imosu[i]
  else:
    if imosu[i] != imosu[i - 1]:
      j += 1
      imosu2[j] = imosu[i]
#print(imosu2)
for i in start:
  x = imosu2.index(i)
  imosu3[x] += 1
#print(imosu3)
for i in end:
  x = imosu2.index(i)
  imosu3[x] -= 1
#print(imosu3)

for i in range(1, 2 * N):
  imosu3[i] += imosu3[i - 1]
#print(imosu3)

ans = 0 
now = 0
for i in range(2 * N):
  #print(i)
  if imosu3[i] > 0:
    now = max(now, imosu3[i])
  else:
    if now >= 2:
      ans += now - 1
      now = 0
    else:
      now = 0

print(N - ans)

Submission status: Time Limit Exceeded

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 = 0
p = 0
while s:
    c += 1
    p = s[0][0]
    s = [i for i in s if i[1] >= p]
print(c)

Submission status: Time Limit Exceeded

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()
Left=[]
for b in B:
  l=b[1];r=b[0]
  flag=1
  for c in Left:
    if (c[0]<l and c[1]>l) or (c[0]<r and c[1]>r):
      flag=0;break   
    elif c[0]>=l and c[1]<=r:
      flag=0;break    
  if flag:
    Left.append([l,r])
print(len(Left))

Submission status: Time Limit Exceeded

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]:
            if d[i][1] in b:
                c[b.index(d[i][1])] = c[j] + 1
            else:
                b.append(d[i][1])
                c.append(c[j]+1)
    
#print(b)
#print(c)

print(max(c))

Submission status: Time Limit Exceeded

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.append(d[i][1])
            c.append(c[j]+1)
    
#print(b)
#print(c)

print(max(c))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a-b,a+b])
L.sort()
L = deque(L)
cnt = 0
for i in range(n-1):
    if L[i][1] > L[i+1][0]:
        cnt +=1
        L.remove(L[i+1])
        L.appendleft([-10**10,-10**10])
print(n-cnt)

Submission status: Time Limit Exceeded

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 >= len(x)-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]
        else:
            del x[i+1]
    else:
        i += 1
print(len(x))

Submission status: Time Limit Exceeded

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] = (i, X - L, X + L)
    robots.sort(key=lambda x: x[2])
    # print(robots)
    remains = []
    for robot in robots:
        # print('remains={}, robot={}'.format(remains, robot))
        conflict = False
        l = robot[1]
        r = robot[2]
        for remain in remains:
            # print(l, r, remain)
            if remain[1] <= l and l < remain[2]:
                # print(robot, remain, l, remain[2], remain[1], r)
                conflict = True
                break
            if remain[1] < r and r < remain[2]:
                # print(robot, remain, l, remain[2], remain[1], r)
                conflict = True
                break
            if l <= remain[1] and remain[1] < r:
                conflict = True
                break
            if l < remain[2] and remain[2] < r:
                conflict = True
                break
        if not conflict:
            remains.append(robot)
    print(len(remains))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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 = indexSort(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: Time Limit Exceeded

Solution code:
n=int(input())

li2=[input() for i in range(n)]
xl = []
for i in range(n):
    xl.append( [int(x.strip()) for x in li2[i].split()])

t = []
t_ = []
for i in range(n):
    t.append(sum(xl[i]))
    t_.append(sum(xl[i]))

ans = 0
use = []
used = list(range(n))
t_.sort()

for i in range(n):
    a = t_[0]
    ind = t.index(a)
    ok = 1


    for j in range(ans):
        #print(xl[used[ind]][0] - xl[used[ind]][1])
        #print(use[j][0] + use[j][1])

        if xl[used[ind]][0] - xl[used[ind]][1] < use[j][0] + use[j][1]:
            #print("b")
            ok = 0
            break


    if ok == 1:
        use.append(xl[ind])
        ans+= 1

    t.pop(ind)
    used.pop(ind)
    t_.pop(0)

print(ans)

Submission status: Time Limit Exceeded

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


def test(array, index, last_position, count, min_count):
    # 除去数が多いパターンは破棄する
    if min_count[0] != -1 and count >= min_count[0]:
        return
    if index + 1 == len(array):
        # print("count:{}".format(count))
        min_count[0] = count if min_count[0] == - \
            1 or count < min_count[0] else min_count[0]
        return
    current = array[index]
    next = array[index + 1]

    # 前か次のと手がぶつかる場合は取り除く
    if last_position >= current[0] - \
            current[1] or current[0] + current[1] >= next[0] - next[1]:
        test(array, index + 1, last_position, count + 1, min_count)
    # 前のとぶつからない場合は取り除かないパターンも
    if last_position < current[0] - current[1]:
        test(array, index + 1, index, count, min_count)


N = int(input())
array = sorted([list(map(int, input().split()))
                for i in range(N)], key=lambda x: x[0])
min_count = [-1]
test(array, 0, -1, 0, min_count)
print(len(array) - min_count[0])

Submission status: Time Limit Exceeded

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


def test(array, index, last_position, count, min_count):
    if index + 1 == len(array):
        # print("count:{}".format(count))
        min_count[0] = count if min_count[0] == - \
            1 or count < min_count[0] else min_count[0]
        return
    current = array[index]
    next = array[index + 1]

    # 前か次のと手がぶつかる場合は取り除く
    if last_position >= current[0] - \
            current[1] or current[0] + current[1] >= next[0] - next[1]:
        test(array, index + 1, last_position, count + 1, min_count)
    # 前のとぶつからない場合は取り除かないパターンも
    if last_position < current[0] - current[1]:
        test(array, index + 1, index, count, min_count)


N = int(input())
array = sorted([list(map(int, input().split()))
                for i in range(N)], key=lambda x: x[0])
min_count = [-1]
test(array, 0, -1, 0, min_count)
print(len(array) - min_count[0])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

l.sort(key = itemgetter(1))
cnt = 0

for i in range(1, N):
  for j in range(i, -N, -1):
    if l[j-1][0] == - 10 ** 9:
      continue
    if l[i][0] < l[j-1][1]:
        l[i][0] = - 10 ** 9
        l[i][1] = - 10 ** 9
        cnt += 1
    break
print(N-cnt)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
ans = []
for i in range(N):
  l[i].append(l[i][0] - l[i][1])
  l[i].append(l[i][0] + l[i][1])
  del l[i][:2]
l.sort(key = itemgetter(1))
cnt = 0
for i in range(1, N):
  for j in range(i, -N, -1):
    if l[j-1][0] == - 10 ** 4:
      continue
    if l[i][0] < l[j-1][1]:
        l[i][0] = - 10 ** 4
        l[i][1] = - 10 ** 4
        cnt += 1
    break
print(N-cnt)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
ans = []
for i in range(N):
  l[i].append(l[i][0] - l[i][1])
  l[i].append(l[i][0] + l[i][1])
  del l[i][:2]
l.sort(key = itemgetter(1))
cnt = 0
for i in range(1, N):
  for j in range(i, -N, -1):
    if l[j-1][0] == - 10 ** 9:
      continue
    if l[i][0] < l[j-1][1]:
        l[i][0] = - 10 ** 9
        l[i][1] = - 10 ** 9
        cnt += 1
    break
print(N-cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
from operator import itemgetter

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
ans = []
for i in range(N):
  l[i].append(l[i][0] - l[i][1])
  l[i].append(l[i][0] + l[i][1])
  del l[i][:2]
l.sort(key = itemgetter(1))

def search(x):
  for i in range(x, len(l)):
    if l[i][0] < l[i-1][1]:
      del(l[i])
      ans.append(1)
      search(x)
      break
search(1)
if ans == []:
  print(N)
else:
  print(N-sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
X = np.zeros([N,2], dtype=int)

for i in range(N):
    X[i] = list(map(int, input().split()))  
left = X[:,0] - X[:,1]
right = X[:,0] + X[:,1]
lr = np.concatenate([left.reshape(-1,1), right.reshape(-1,1)], 1)

r_min = np.argmin(right)
use = lr[r_min].reshape(-1,2)
while use[-1,1] <= np.max(left):
    lr = lr[np.all(lr >= use[-1,1], axis=1),:]
    r_min = np.argmin(lr[:,1])
    use = np.vstack([use, lr[r_min]])
print(len(use))

Submission status: Time Limit Exceeded

Solution code:
_, *_XL = open(0).read().split()

XL = list(zip(*[map(int, iter(_XL))]*2))

ans = 0
t = -10**10 # 数直線のマイナス方向からスタートする

arms = [(X-L, X+L) for X, L in XL]

arms_sorted = sorted(arms, key=lambda k:k[1])

for s, e in arms_sorted:
    if t <= s:
        t = e
    else:
        arms.remove((s, e))

print(len(arms))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
R = [list(map(int, input().split())) for i in range(N)]
T = [[R[i][0] + R[i][1], R[i][0] - R[i][1]] for i in range(N)]
T.sort()
while len(T) - 1 > 0:
    t = T.pop(0)
    i = 1
    while len(T) and t[0] > T[0][1]:
        N -= 1
        i += 1
        T.pop(0)
print(N)

Submission status: Time Limit Exceeded

Solution code:
_, *_XL = open(0).read().split()

XL = list(zip(*[map(int, iter(_XL))]*2))

ans = 0
t = -10**10 # 数直線のマイナス方向からスタートする

arms = [(X-L, X+L) for X, L in XL]

for s, e in sorted(arms, key=lambda k:k[1]):
    if t <= s:
        t = e
    else:
        arms.remove((s, e))

print(len(arms))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
R = sorted([list(map(int, input().split())) for i in range(N)])
T = []
for i in range(N):
    T.append([R[i][0] + R[i][1], R[i][0] - R[i][1]])
T.sort()
while len(T) - 1 > 0:
    t = T.pop(0)
    i = 1
    while len(T) and t[0] > T[0][1]:
        N -= 1
        i += 1
        T.pop(0)
print(N)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
R = sorted([list(map(int, input().split())) for i in range(N)])
T = []
for i in range(N):
    T.append([R[i][0] + R[i][1], R[i][0] - R[i][1]])
T.sort()
while len(T) - 1 > 0:
    t = T.pop(0)
    i = 1
    while len(T) and t[0] > T[0][1]:
        N -= 1
        i += 1
        T.pop(0)
print(N)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter, defaultdict
from itertools import permutations
import heapq


def resolve():
    N = int(sys.stdin.readline().strip())
    pq = []
    for _ in range(N):
        X, L = map(int, sys.stdin.readline().strip().split())
        heapq.heappush(pq, (X + L, X - L))
    ans = 0
    while pq:
        ans += 1
        right, _ = heapq.heappop(pq)
        if pq:
            _, next_left = min(pq)
            while next_left < right:
                heapq.heappop(pq)
                if not pq:
                    break
                _, next_left = min(pq)

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    L = []
    for i in range(N):
        xi, li = map(int, input().split())
        s = xi - li
        f = xi + li
        L.append((s, f))
    
    L.sort(key=lambda x: x[1])

    ans = 0
    while L:
        e = L[0]
        L = [i for i in L if i[0] >= e[1]]
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def trush(XL):
    pt,output = 1,len(XL)
    while pt < len(XL)-1:
        if XL[pt-1][2] > XL[pt][1] and XL[pt][2] > XL[pt+1][1]:
            XL = XL[:pt] + XL[pt+1:]
            output -= 1
        else:
            pt += 1

    pt = 0
    while pt < len(XL)-1:
        if XL[pt][2] > XL[pt+1][1]:
            if XL[pt][0]-XL[pt][1] > XL[pt+1][0]-XL[pt+1][1]:
                XL = XL[:pt] + XL[pt+1:]
            else:
                XL = XL[:pt+1] + XL[pt+2:]
            output -= 1
        else:
            pt += 1

    return output

def main():
    N = int(input())
    XL = [list(map(int,input().split())) for _ in range(N)]
    for i in range(N):
        XL[i] = [XL[i][0],XL[i][0]-XL[i][1],XL[i][0]+XL[i][1]]
    XL.sort(key = lambda x:x[0])
    
    ans = trush(XL)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = input()
N = int(N)
X = [0] * N
L = [0] * N
Left = [0] * N
Right = [0] * N

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

ans = 0
maxX = -1000000000
for i in range(N):
    minIdxTmp = Right.index(min(Right))
    if(maxX <= Left[minIdxTmp]):
        maxX = Right[minIdxTmp]
        ans += 1
    Right.pop(minIdxTmp)
    Left.pop(minIdxTmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xl = [[0]*2 for _ in range(n+1)]
xl[0][0] = -10**9
xl[0][1] = -10**9
for i in range(n):
  a,b = list(map(int,input().split()))
  xl[i+1][0] = a - b
  xl[i+1][1] = a + b
xl = sorted(xl)

def dist(bit):
  pre = 0
  for i in range(1,n+1):
    if bit & 1<<i:
      if xl[pre][1] > xl[i][0]:
        return False
      pre = i
  return True

if dist((1<<(n+1))-1):
  print(n)
  exit()

def bi():
  for bit in range(1<<(n+1))[::-1]:
    if bit & 1<<n:
      if dist(bit):
        print(sum([1 for i in range(n+1) if bit & 1<<i])-1)
        #print(bin(bit),sum([1 for i in range(n+1) if bit & 1<<i])-1)
        exit()
bi()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
XL = [list(map(int,input().split())) for _ in range(n)]
XL = sorted(XL)
xl = [[0]*2 for _ in range(n+1)]
xl[0][0] = -10**9
xl[0][1] = -10**9
for i in range(n):
  xl[i+1][0] = XL[i][0] - XL[i][1]
  xl[i+1][1] = XL[i][0] + XL[i][1]

def dist(bit):
  pre = 0
  for i in range(1,n+1):
    if bit & 1<<i:
      if xl[pre][1] > xl[i][0]:
        return False
      pre = i
  return True

if dist((1<<(n+1))-1):
  print(n)
  exit()

def bi():
  for bit in range(1<<(n+1))[::-1]:
    if bit & 1<<n:
      if dist(bit):
        print(sum([1 for i in range(n+1) if bit & 1<<i])-1)
        #print(bin(bit),sum([1 for i in range(n+1) if bit & 1<<i])-1)
        exit()
bi()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
XL = [list(map(int,input().split())) for _ in range(n)]
XL = sorted(XL)
xl = [[0]*2 for _ in range(n+1)]
xl[0][0] = -10**9
xl[0][1] = -10**9
for i in range(n):
  xl[i+1][0] = XL[i][0] - XL[i][1]
  xl[i+1][1] = XL[i][0] + XL[i][1]

def dist(bit):
  flg = True
  pre = 0
  for i in range(1,n+1):
    if bit & 1<<i and i > 0:
      if xl[pre][1] > xl[i][0]:
        flg = False
      pre = i
  return flg

if dist((1<<(n+1))-1):
  print(n)
  exit()

ans = 0
for bit in range(1<<(n+1))[::-1]:
  if bit & 1<<n:
    if dist(bit):
      print(sum([1 for i in range(n+1) if bit & 1<<i])-1)
      #print(bin(bit),sum([1 for i in range(n+1) if bit & 1<<i])-1)
      exit()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from itertools import permutations

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

XL = sorted(XL, key=itemgetter(0))

for i in range(N):
    for remove in permutations(XL, i):
        remained = [i for i in XL if i not in remove]
        edge = []
        for remain in remained:
            x, l = remain
            edge.append(x-l)
            edge.append(x+l)
        if edge == sorted(edge):
            print(len(remained))
            exit()