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: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
r = []
for i in range(n):
    x, l = map(int, input().split())
    r.append((x - l + 1, x + l - 1))
r.sort()
am = [[] for _ in range(n)]
for i in range(n):
    for j in range(i + 1, n):
        if r[i][1] >= r[j][0]:
            am[i].append(j)
            am[j].append(i)
while sum(len(mi) for mi in am):
    maxi, maxd = 0, 0
    for i, mi in enumerate(am):
        li = len(mi)
        if li > maxd:
            maxi, maxd = i, li
    for pi in am[maxi]:
        am[pi].remove(maxi)
    am.pop(maxi)
    n -= 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

robotLEFT=[]
robotRIGHT={}

for _ in range(n):
    x,l=map(int,input().split())
    if x-l not in robotLEFT:
        robotLEFT.append(x-l)
        robotRIGHT[x-l]=x+l
    else:
        robotRIGHT[x-l]=min(robotRIGHT[x-l],x+l)

robotLEFT.sort()
#print(robotRIGHT)
#print(robotLEFT)

temp=robotLEFT[0]
LL=temp-2
RR=temp-1
cnt=0

for item in robotLEFT:
    #print(LL,RR,cnt)
    if RR<=item:
        cnt+=1
        LL=item
        RR=robotRIGHT[LL]
    else:
        if RR>=robotRIGHT[item]:
            RR=robotRIGHT[item]
            LL=item
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H=int(input())
K=H
a=[]
b=[0]*H
k=1
s=0

for i in range(H):
  a.append(list(map(int,input().split())))

  
while k!=0:
  b=[0]*H
  k=0
  for i in range(H):
    for c in range(H):
      if i!=c:
         if abs(a[i][0]-a[c][0])<a[i][1]+a[c][1]:
            b[i]+=1
  for i in range(H):
    k+=b[i]
    
  if k!=0:
    a.pop(b.index(max(b)))
    s+=1
    H-=1

print(K-s)

Submission status: Time Limit Exceeded

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

temp = [x for x in range(n)]
ans = 0
cnt = 0
li.sort()

while True:
    arr = []
    check = -10**10
    for i in temp:
        s = li[i][0] - li[i][1]
        if check > s:
            if i-1 not in arr:
                arr.append(i-1)
            if i not in arr:
                arr.append(i)
        check = li[i][0] + li[i][1]
    else:
        if len(arr) == 0:
            break
        temp = arr
        t = -2
        for index,i in enumerate(arr):
            if t == -2:
                t = i
            elif t+1 == i:
                del temp[index]
                t = -2
                ans += 1
            else:
                t = i

print(n-ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
r = [[int(i) for i in input().split()] for i in range(n)]
arm_dict = {}
for a in r:
    arm = (a[0] - a[1], a[0] + a[1])
    for c in range(arm[0], arm[1]):
        if c in arm_dict.keys():
            arm_dict[c] += 1
        else:
            arm_dict[c] = 1
max_v = max(arm_dict.values())
ans = n - max_v + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
x = sorted([list(map(int, input().split())) for i in range(n)])
y = copy.deepcopy(x)

j = 0
while j < len(x)-1:
    if x[j][0]+x[j][1] > x[j+1][0]-x[j+1][1]:
        y.pop(j+1)
        j += 2
        continue
    j += 1

print(len(y))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
X = []
L = []
for _ in range(n):
    x, l = map(int, input().split())
    X.append(x)
    L.append(l)
X = sorted(set(X), key=X.index)

areas = [(x - l, x + l)for x, l in zip(X, L)]
for i, (m0, M0) in enumerate(areas):
    for m, M in (areas[:i] + areas[i+1:]):
        if (m0 <= m) and (M <= M0):
            areas.pop(i)
# print(areas)

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

for area in areas:
    if not areas2:
        areas2.append(area)
    elif areas2[-1][-1] <= area[0]:
        areas2.append(area)

# print(areas)
# print(areas2)

print(len(areas2))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

def check(ax,al,bx,bl):
    if ax + al <= bx - bl or bx + bl <= ax - al:
        return True
    return False

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

remove = 0
while True:
    remain = len(X)
    conflict = [[] for i in range(remain)]
    index = list(itertools.combinations(range(remain), 2))

    noConf = True

    for a,b in index:
        if check(X[a],L[a],X[b],L[b]):
            None
        else:
            noConf = False
            conflict[a].append(b)
            conflict[b].append(a)

    if noConf == True:
        break


    while True:
        if conflict == [[] for i in range(remain)]:
            break
        else:
            remInd = []
            lens = []
            for n in range(remain):
                lens.append(len(conflict[n]))
            newInd = lens.index(max(lens))
            remInd.append(newInd)
            remove += 1
            for i in conflict[newInd]:
                conflict[i].remove(newInd)
            conflict[newInd] = []

    for n in remInd:
        X[n] = -1
        L[n] = -1

    X = [i for i in X if i == -1]
    L = [i for i in L if i == -1]

print(N - remove)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
r = [[int(i) for i in input().split()] for i in range(n)]
arm_dict = {}
for i, a in enumerate(r):
    arm = (a[0] - a[1], a[0] + a[1])
    for c in range(arm[0], arm[1]):
        if c in arm_dict.keys():
            arm_dict[c] += 1
        else:
            arm_dict[c] = 1
max_v = max(arm_dict.values())
ans = n - max_v + 1
# print(arm_dict)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
list = [input().rstrip().split() for _ in range(N)]
list = [[int(list[i][0]),int(list[i][1])] for i in range(N)]
list.sort(key=lambda x: x[0])

def hit_count(list):
  list2 = [[int(list[i][0])-int(list[i][1]), int(list[i][0])+int(list[i][1])] for i in range(len(list))]
  return [list2[i+1][0] - list2[i][1] for i in range(len(list)-1)]
list3 = hit_count(list)


i = 0
while(len([i for i in list3 if i <0]) >0):
  list3 = hit_count(list)
  if len(list3) == 0:
    break
  if list3[i] < 0:
    if i ==0:
      list.pop(1)
    elif i == len(list3):
      list.pop(len(list3)-1)      
    elif list[i][1] >= list[i+1][1]:
      list.pop(i-1)
    elif list[i][1] < list[i+1][1]:
      list.pop(i)
    i=0
  i += 1
    
print(len(list))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l,k,m=[],[],[]
for i in range(n):
    a,b=map(int,input().split())
    l+=[a];k+=[a];m+=[b]
l.sort()
a,b=[],[]
for i in l:
    a+=[i]
    b+=[m[k.index(i)]]
l=0
i=0
while i<n-1:
    if a[i]+b[i]>a[i+1]-b[i+1]:
        l+=1
        i+=1
    i+=1
print(n-l)

Submission status: Time Limit Exceeded

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

value = []
for i in range(N):
  l = 0
  for j in range(i):
    if robots[i][0]-robots[i][1]<robots[j][0]+robots[j][1] : l += 1
  for j in range(i+1,N):
    if robots[i][0]+robots[i][1]>robots[j][0]-robots[j][1]: l += 1
  value.append(l)
  
cover = sum(value)//2
while cover != 0:
  cover -= max(value)
  value.remove(max(value))

print(len(value))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
rx = {}

minrx = 10 ** 10
minrx_idx = -1
for i in range(n):
    xx, ll = map(int, input().split(' '))
    rx[xx - ll] = (xx - ll, xx + ll)

rxs = sorted(rx.items(), key=lambda x:x[0])

rxs_ = [i[1] for i in rxs]

max_cnt = 0

for s in range(n):
    if max_cnt >= n - s + 1:
        break

    rxs2 = rxs_[s:]

    now_idx = 0
    cnt = 1
    for i, x in enumerate(rxs2):
        if now_idx == i:
            continue
        if rxs2[now_idx][1] > rxs2[i][0]:
            continue
        now_idx = i
        cnt += 1

    if max_cnt < cnt:
        max_cnt = cnt

print(max_cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  xl = []
  ans = 0
  for i in range(n):
    xl.append(list(map(int, input().split())))
    xl.sort(key = lambda x:x[1])
    road = set()
  for i in range(n):
    sub = {}
    location = xl[i][0]
    arm = xl[i][1]
    sub = {j for j in range(max(0, location-arm+1), location+arm)}
    num_sub = len(sub)
    num_road = len(road)
    Z = road|sub
    if len(Z) ==num_sub + num_road:
      road = Z
      ans += 1

  print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def dist(arm1, arm2):
  d = arm2[0] - arm1[0]
  a = arm2[1] + arm1[1]
  if d<a:
    return False
  else:
    return True


N = int(input())
array = []
for x in range(N):
  array.append(list(map(int, input().split())))
  array = sorted(array, key = lambda x:x[0])
  #print(array)
if N==1:
  print(1)
elif N==2:
  if dist(array[0], array[1]):
    print(2)
  else:
    print(1)
else:
  
  count = 0
  for p in range(1, N-1):
    if dist(array[p-1], array[p]) or dist(array[p], array[p+1]):
      count += 1
  
  print(count+2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]
import numpy as np

ls = np.array([[i-j, i+j] for i, j in xl])
ls = ls[ls[:, 0].argsort()]
i, dr = 0, 0
while True:
    if len(ls)<=1:
        break
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls = np.delete(ls, i+1, 0)
    else:
        i += 1
        if i+1 >= len(ls):
            break
print(len(ls))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def have_common(di, dj):
    """2つの区間di, djが共通部分を持つかどうかを判定
    """
    if dj[0] < di[0]:
        di, dj = dj, di
    if dj[0] < di[1]:
        return True
    else:
        return False

N = int(input())

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

Con = []  # 共通部分を持つペア
Con_count = [0] * N
ans = N

for j in range(N-1):
    for k in range(j+1, N):
        if have_common(D[j], D[k]):
            Con.append([j, k])
            Con_count[j] += 1
            Con_count[k] += 1

while (Con != []):
    ind = np.argmax(Con_count)
    # ind 番目の区間を消去
    ans -= 1
    Con = [i for i in Con if ind not in i]
    Con_count[ind] = 0

print(ans)

Submission status: Time Limit Exceeded

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

def calc(r, a):
  x = a[0]
  l = a[1]
  
  cnt = 0
  for b in r:
    bx = b[0]
    bl = b[1]
    if ((x - l + 1) <= (bx - bl + 1) and (bx - bl + 1) <= (x + l - 1)) or ((x - l + 1) <= (bx + bl - 1) and (bx + bl - 1) <= (x + l - 1)):
      cnt += 1
  cnt -= 1
  return cnt

def check(r):
  for a in r:
    if calc(r, a) != 0:
      return False
  return True

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

for a in r:
  a.append(calc(r, a))

while not check(r):
  r.pop(0)

print(len(r))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
X=[]
ans=0
for i in range(N):
    H = list(map(int, input().split()))
    O=[]
    O.append(H[0]-H[1])
    O.append(H[0]+H[1])
    X.append(O)
#print(X)
X=sorted(X, key=itemgetter(1))
while(len(X)>0):
    #print(X)
    ans+=1
    S=X[0][1]
    X.remove(X[0])
    I = []
    for i in range(len(X)):
        if(X[i][0]>=S):
            I.append(X[i])
    X=I
    #print(I)



print(ans)

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
X=[]
L=[]
for i in range(1,N+1):
    x, l=map(int,input().split())
    X.append(x)
    L.append(l)
A=N
c=0

X.sort()

Check=[[X[i]-L[i],X[i]+L[i]] for i in range(N)]

for j in range(1,N):
    if j == N:
        break
    if Check[j-1][1] > Check[j][0]:
        c=c+1
        Check.remove(Check[j])
        j=j-1
        N=N-1
    
print(A-c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xl=[list(map(int,input().split())) for _ in range(n)]
xl.sort(key=lambda x: x[0])
ans=0
for i in range(n):
  xi,li=xl[i]
  cnt=1
  for j in range(n):
    xj,lj=xl[j]
    if xi+li<=xj-lj:
      cnt+=1
      xi=xj
      li=lj
  ans=max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XL = []
flag = [0]*N
for i in range(N):
	xl = list(map(int,input().split()))
	XL.append(xl)
XL.sort()
for i in range(N-1):
	for j in range(i+1,N-i):
		if(flag[i] == 0 ):
			if(XL[i][0]+XL[i][1]>=XL[j][0]):
				flag[j]=1
			else:
				break
sum = 0
for i in range(N):
	sum+=flag[i]
print(N-sum)

Submission status: Time Limit Exceeded

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

n = int(input())
a = []
b = []
b2 = []
c = []
count = 0

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append([x,y,x+y])

a.sort(key=lambda x: x[2])

for i in a:
    c = b.copy()
    b.extend(list(range(i[0]-i[1], i[0]+i[1])))
    b2 = b.copy()
    b = list(set(b))
    if len(b2) != len(b):
        b = c.copy()
        count += 1
    
print(n - count)

Submission status: Time Limit Exceeded

Solution code:
H=int(input())
K=H
a=[]
b=[0]*H
k=1
s=0

for i in range(H):
  a.append(list(map(int,input().split())))

  
while k!=0:
  b=[0]*H
  k=0
  for i in range(H):
    for c in range(H):
      if i!=c:
        if a[i][0]>a[c][0]:
          if a[i][0]-a[i][1]<a[c][0]+a[c][1]:
             b[i]+=1
        else:
          if a[i][0]+a[i][1]>a[c][0]-a[c][1]:
             b[i]+=1


  for i in range(H):
    k+=b[i]
    
  if k!=0:
    a.pop(b.index(max(b)))
    s+=1
    H-=1

print(K-s)

Submission status: Time Limit Exceeded

Solution code:
def isdouble(set_list):
    for i,s in enumerate(set_list):
        if i-1 in s or i+1 in s:
            return True
    return False
n=int(input())
robots = []
for _ in range(n):
    x,arm = map(int, input().split())
    robots.append([num for num in range(x-arm,x+arm,1)])
double=[set() for _ in range(len(robots))]
for i in range(len(robots)):
    for j in range(len(robots)):
        if i!=j and set(robots[i]) & set(robots[j]):
             double[i].add(j)
#print(double)
count=0
#print(max([len(s) for s in double]))
while isdouble(double):
    m=max([len(s) for s in double])
    for i,s in enumerate(double):
        if len(s)==m:
            break
    double[i]=set()
    for j,s in enumerate(double):
        if i in s:
            #print('>>',s,set([i]))
            double[j] = s-set([i])
            #print('>>',double)
    count+=1
print(len(robots)-count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys #追加
    sys.setrecursionlimit(500*500) #追加
    n = int(input())

    x = []
    l = []
    tls = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        x.append(tmp[0])
        l.append(tmp[1])
    x, l = zip(*sorted(zip(x, l)))

    m = {}
    def solve(prev, idx):
        if idx == n:
            return 0
        key = (prev, idx)
        if key in m:
            return m[key]
        res_use = 0
        res_nouse = 0
        if idx < n - 1:
            if x[idx] + l[idx] >= x[idx+1] + l[idx+1]: 
                return solve(prev, idx+1)
        if x[idx] - l[idx] >= prev or prev == 0:
            res_use = 1
            res_use += solve(x[idx] + l[idx], idx + 1)
        res_nouse += solve(prev, idx + 1)

        ans = max(res_use, res_nouse)
        m[key] = ans
        return ans
    print(solve(0, 0))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xl = []
ans = 0
for i in range(n):
  xl.append(list(map(int, input().split())))
xl.sort(key = lambda x:x[1])
road = set()
for i in range(n):
  sub = {}
  location = xl[i][0]
  arm = xl[i][1]
  sub = {j for j in range(max(0, location-arm+1), location+arm)}
  num_sub = len(sub)
  num_road = len(road)
  Z = road|sub
  if len(Z) ==num_sub + num_road:
    road = Z
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XL = []
flag = [0]*N
for i in range(N):
	xl = list(map(int,input().split()))
	XL.append(xl)
XL.sort()
for i in range(N-1):
	for j in range(i+1,N-i):
		if(flag[i] == 0 ):
			if(XL[i][0]+XL[i][1]>=XL[j][0]):
				flag[j]=1
sum = 0
for i in range(N):
	sum+=flag[i]
print(N-sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]
import numpy as np

ls = np.array([[i-j, i+j] for i, j in xl])
ls = ls[ls[:, 0].argsort()]

i, dr = 0, 0
while i in range(len(ls)-1):
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls = np.delete(ls, i+1, 0)
    else:
        i += 1
        if i >= len(ls):
            break
print(len(ls))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    robots = list()
    hit_cnt = list()
    for n in range(N):
        X, L = map(int, input().split(' '))
        robots.append([X - L, X + L])
        hit_cnt.append([])
        for i in range(n):
            if ((robots[i][0] < X) and (X < robots[i][1])) or ((robots[i][0] < X + L) and (X + L < robots[i][1])) or (
                    (robots[i][0] < X - L) and (X - L < robots[i][1])):
                hit_cnt[i].append(n)
                hit_cnt[n].append(i)
    while [] in hit_cnt:
        hit_cnt.remove([])
    while len(hit_cnt) > 0:
        maximum_hit = 0
        index = -1
        for enum, hit in enumerate(hit_cnt):
            if len(hit) > maximum_hit and len(hit) > 0:
                maximum_hit = len(hit)
                index = enum
        if index == -1:
            break
        robots.pop(index)
        hit_cnt.pop(index)
        for enum, hit in enumerate(hit_cnt):
            if index in hit:
                hit_cnt[enum].remove(index)
        while [] in hit_cnt:
            hit_cnt.remove([])
    print(len(robots))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a=[0]*n
b=[0]*n


for i in range(n):
    a[i],b[i]=x[i]-l[i],x[i]+l[i]
    
cnt=0    
while(b):
    bm=min(b)
    
    a.pop(b.index(min(b)))
    b.pop(b.index(min(b)))
    cnt+=1
    while(b and a[b.index(min(b))]<bm):
        a.pop(b.index(min(b)))
        b.pop(b.index(min(b)))


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[]
L=[]
XA=[]
XB=[]
Q=[0]*N
take=0
for i in range(N):
  x,l=map(int,input().split())
  X.append(x)
  L.append(l)
for i in range(N):
  XA.append(X[i]-L[i])
  XB.append(X[i]+L[i])
S=list(zip(XA,XB))
S.sort()
#print(S)

for i in range(N-1):
  cnt=0
  for j in range(i+1,N):
    if S[i][1]>S[j][0]:
      cnt=cnt+1
  Q[i]=Q[i]+cnt
#print(Q)
p=0
k=0
while p!=N-1:
  if Q[p]!=0:
    k=k+1
    if p+2>N-1:
      break
    else:
      p=p+2
  else:
    p=p+1
print(N-k)

Submission status: Time Limit Exceeded

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

bounds = 0
c = 0
ts = []
for i in range(n):
    if bounds != 0 and bounds > (xl[i][0]-xl[i][1]+1):
        if i == 1 and (xl[i][0] - xl[i][1] + 1) < (xl[i-1][0] + xl[i-1][1] - 1):
            c -= 1
        ts.append(xl[i])
    else:
        c += 1
    bounds = xl[i][0] + xl[i][1] - 1

ans = 0
for b in range(2**(len(ts))):
    flag = True
    bounds = 0
    for i in range(len(ts)):
        if (b>>i)&1:
            if bounds != 0 and bounds > (ts[i][0]-ts[i][1]+1):
                flag = False
                break
            bounds = ts[i][0] + ts[i][1] - 1
    if flag:
        ans = max(ans, bin(b).count("1")+c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
rx = {}

minrx = 10 ** 10
minrx_idx = -1
for i in range(n):
    xx, ll = map(int, input().split(' '))
    rx[xx - ll] = (xx - ll, xx + ll)

rxs = sorted(rx.items(), key=lambda x:x[0])

rxs_ = [i[1] for i in rxs]

max_cnt = 0

for s in range(n):
    if max_cnt >= n - s + 1:
        break

    rxs2 = rxs_[s:]

    now_idx = 0
    cnt = 1
    for i, x in enumerate(rxs2):
        if now_idx == i:
            continue
        if rxs2[now_idx][1] > rxs2[i][0]:
            continue
        now_idx += 1
        cnt += 1

    if max_cnt < cnt:
        max_cnt = cnt

print(max_cnt)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
X=[]
ans=0
for i in range(N):
    H = list(map(int, input().split()))
    O=[]
    O.append(H[0]-H[1])
    O.append(H[0]+H[1])
    X.append(O)
#print(X)
while(len(X)>0):
    X=sorted(X, key=itemgetter(1))
    #print(X)
    ans+=1
    S=X[0][1]
    X.remove(X[0])
    I = []
    for i in range(len(X)):
        if(X[i][0]>=S):
            I.append(X[i])
    X=I
    #print(I)



print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
X = []
L = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    L.append(y1)
flag=0
for i in range(N-1):

    pointp=X[i]+L[i]
    pointm=X[i]-L[i]
    for j in range(i+1,N):
        if X[j]<=X[i]:
            if X[j]+L[j]>pointm:
                flag+=1
        elif X[j]>X[i]:
            if X[j]-L[j]<pointp:
                flag+=1
    
print(N-math.ceil(flag/2))

Submission status: Time Limit Exceeded

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

n = int(input())
list = [list(map(int, input().split())) for i in range(n)]
ans = []
list.sort(key=lambda x: x[0])


for i in range(n-1):
    if not(list[i][0] in ans):
        if list[i][0] + list[i][1] > list[i+1][0] - list[i+1][1]:
            ans.append(list[i+1][0])
    elif list[i-1][0] + list[i-1][1] > list[i+1][0] - list[i+1][1]:
         ans.append(list[i+1][0])
print(n - len(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    L = [list(map(int, input().split())) for _ in range(N)]
    tmp = []
    for a, b in L:
        tmp.append([a-b, a+b, 0])
    tmp.sort()
    ty, tc = 0, N
    c = 0

    for i in range(N):
        for j in range(i, N):
            if tmp[i][0] < tmp[j][0] < tmp[i][1]:
                tmp[i][2] += 1
            elif tmp[i][0] < tmp[j][1] < tmp[i][1]:
                tmp[i][2] += 1

    flg = 0
    for i in range(N):
        if tmp[i][2] > 0:
            flg = 1
            if tc > tmp[i][2]:
                ty, tc = tmp[i][1], tmp[i][2]
        else:
            if flg:
                if tmp[i][0] >= ty:
                    c += 1
                flg = 0
            tc = N
            c += 1

    print(c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# 左端でソート
XP = sorted([(x-l, x+l) for x, l in zip(X, L)], key=lambda x: x[0])

X1 = [x[0] for x in XP]
X2 = [x[1] for x in XP]

def find(xs, t):
    for i, x in enumerate(xs):
        if t <= x:
            return i
    return -1


# 左端indexを指定
i1 = 0
count = 0
while i1 < N:
    right = X2[i1]
    i_pick = i1
    for i2 in range(i1+1, N):
        # より短いなら
        if X2[i2] < right:
            right = X2[i2]
            i_pick = i2

    count += 1
    # right より右で 最小のX1のindex
    i1 = find(X1, right)
    if i1 == -1:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline
    N = int(input())

    robots = dict()
    x_list = []
    duplicates = dict()

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

    x_list.sort()
    n_duplicates = 0

    for i, x in enumerate(x_list):
        arm = robots[x]
        for y in x_list[i:]:
            if x == y:
                continue
            if x+arm > y-robots[y]:
                duplicates[x] += 1
                duplicates[y] += 1
                n_duplicates += 2

    n_d_list = sorted(duplicates.values(), reverse=True)
    count = 0
    for d in n_d_list:
        if n_duplicates < 1:
            break
        n_duplicates -= 2 * d
        count += 1

    print(N - count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#input = raw_input
import numpy as np
n = int(input())

jamas = [[] for _ in range(n)]
jamas_count = [0 for _ in range(n)]

xs = []
ls = []
for i in range(n):
    x, l = map(int, input().split(" "))
    xs.append(x)
    ls.append(l)

    for j in range(0, i):
        if xs[j] < x:
            x1 = xs[j]
            l1 = ls[j]
            x2 = x
            l2 = l
        else:
            x1 = x
            l1 = l
            x2 = xs[j]
            l2 = ls[j]
        if x1 + l1 - 1 < x2 - l2 + 1:
            pass
        else:
            jamas[i].append(j)
            jamas[j].append(i)
            jamas_count[i] += 1
            jamas_count[j] += 1


def argmax(jamas_count):
    max_jama = max(jamas_count)
    max_i = jamas_count.index(max_jama)
    return max_i


def find_max_jama():
    max_i = np.argmax(jamas_count)
    return max_i

n_remove = 0
while True:
    max_i = find_max_jama()

    jama_count = jamas_count[max_i]

    if jama_count == 0:
        break

    aites = jamas[max_i]
    for aite in aites:
        if jamas_count[aite] == 0:
            continue
        #jamas[aite].remove(max_i)
        jamas_count[aite] -= 1

    #jamas[max_i] = []
    jamas_count[max_i] = 0
    n_remove += 1

out = n - n_remove
print(out)

Submission status: Time Limit Exceeded

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

ok = [True for _ in range(n)]

def f(i):
    rs = []
    for j in range(n):
        if i == j or not ok[j]:
            continue
        if xs[i] - ls[i] < xs[j] + ls[j] and xs[j] - ls[j] < xs[i] + ls[i]:
            rs.append(j)
    return rs

for i in range(n):
    if not ok[i]:
        continue

    rs = f(i)
    if len(rs) == 1:
        j = rs[0]
        ts = f(j)
        if len(ts) == 0:
            ok[i] = False
        else:
            ok[j] = False
    elif len(rs) > 1:
        ok[i] = False

c = 0
for v in ok:
    if v:
        c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

X_list = []
L_list = []

for i in range(N):
    x1,l1=[int(i) for i in input().split()]
    X_list.append(x1)
    L_list.append(l1)

def get_batting_count_list(X_list,L_list):
  batting_count_list = []
  for i in range(len(X_list)):
    batting_count = 0
    for j in range(len(X_list)):
      if(i != j):
        if(abs(X_list[i]-X_list[j]) < L_list[i]+L_list[j]):
          batting_count += 1
    batting_count_list.append(batting_count)
  return batting_count_list

while True:
  batting_count_list = get_batting_count_list(X_list, L_list)
  max_batting_count = max(batting_count_list)
  if(max_batting_count != 0):
    max_index = batting_count_list.index(max_batting_count)
    X_list.pop(max_index)
    L_list.pop(max_index)
  else:
    break

print(len(X_list))

Submission status: Time Limit Exceeded

Solution code:
def isdouble(set_list):
    for s in set_list:
        if len(s)!=0:
            return True
    return False
n=int(input())
robots = []
for _ in range(n):
    x,arm = map(int, input().split())
    robots.append([num for num in range(x-arm,x+arm,1)])
double=[set() for _ in range(len(robots))]
for i in range(len(robots)):
    for j in range(len(robots)):
        if i!=j and set(robots[i]) & set(robots[j]):
             double[i].add(j)
#print(double)
count=0
#print(max([len(s) for s in double]))
while isdouble(double):
    m=max([len(s) for s in double])
    for i,s in enumerate(double):
        if len(s)==m:
            break
    double[i]=set()
    for j,s in enumerate(double):
        if i in s:
            #print('>>',s,set([i]))
            double[j] = s-set([i])
            #print('>>',double)
    count+=1
print(len(robots)-count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

X, L = [-10**9-1], [0]
for _ in range(N):
  x, l = map(int, input().split())
  X.append(x)
  L.append(l)
X.append(10**9 + 1)
L.append(0)
X.sort()
L.sort()

while True:
  C = [0 for _ in range(len(X))]
  for i in range(1, len(X)-1):
    if X[i-1] + L[i-1] > X[i] - L[i]:
      #print('left corre: ', X[i-1] + L[i-1], X[i] - L[i])
      C[i] += 1
    if X[i+1] - L[i+1] < X[i] + L[i]:
      #print('left corre: ',X[i+1] - L[i+1], X[i] + L[i])
      C[i] += 1
  #print('before: ', X, L, C)
  
  if max(C):
    max_index = C.index(max(C))
    _ = X.pop(max_index)
    _ = L.pop(max_index)
    _ = C.pop(max_index)
    #print('after: ', X, L, C)
    
  if not max(C):
    break
  
print(len(X)-2)