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:
n = int(input())
robot = [
    list(map(int, input().split())) for i in range(n)
]
robot.sort(key=lambda x: x[1], reverse=True)
ans = []
now = set()

for i in range(n):
    robot_i = robot.pop()
    i_range = set(range(
        robot_i[0]-robot_i[1], robot_i[0]+robot_i[1]
    ))
    if len(now.intersection(i_range)) == 0:
        now = now.union(i_range)
        ans.append(robot_i)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math
import collections


def main():
    n = int(input())
    inputs = [input() for i in range(n)]
    inputs_list = []
    for s in inputs:
        tmp = s.split(' ')
        if int(tmp[0]) - int(tmp[1]) < 0:
            for i in range(0, int(tmp[0]) + int(tmp[1])):
                inputs_list.append(i)
        else:
            for i in range(int(tmp[0]) - int(tmp[1]), int(tmp[0]) + int(tmp[1])):
                inputs_list.append(i)

    c = collections.Counter(inputs_list)
    print(n - (c.most_common()[0][1] - 1))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
lis = []
X = []
ans = []
for i in range(N):
    x,l = map(int, input().split(" "))
    lis.append((x-l,x+l))
    X.append(x)
s = []
for i in range(N):
    cnt = 0
    for j,v in enumerate(lis):
        a,b = v
        if i == j:
            continue
        else:
            if a < X[i] < b:
                cnt += 1
    if cnt == 0:
        ans.append(lis[i])
    if cnt == 1:
        s.append(lis[i])
print(len(ans) + len(s)//2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()

i = 1

while len(X)>i:
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        if max_2 >= max_1:
            d.pop(x_2, None)
            d.pop(x_2, None)
            X.pop(i)
            i -= 1
        else:
            d.pop(x_1, None)
            d.pop(x_1, None)
            X.pop(i-1)
            i -= 1

    i += 1
ans = len(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
max_num = 1000000000

N = int(input())

robots = []
conflict_counts = []
for _ in range(N):
  x, l = map(int, input().split())
  robot = {}
  start = x - l + 1
  start = start if 0 < start else 0 
  end = x + l -1
  end = end if end < max_num else max_num
  robot['start'] = start
  robot['end'] = end
  robot['conflict_ids'] = []
  robot['removed'] = False
  robots.append(robot)
  conflict_counts.append(0)

robots = sorted(robots, key=lambda x:x['end'])
robots = sorted(robots, key=lambda x:x['start'])

for i in range(N-1):
  ckeck_target = robots[i]
  end = ckeck_target['end']

  for j in range(i+1, N):
    if j in ckeck_target['conflict_ids']:
      continue
    compare = robots[j]
    if compare['start'] <= end:
      for s in range(i, j)[::-1]:
        robots[s]['conflict_ids'].append(j)
        conflict_counts[s] += 1
        compare['conflict_ids'].append(s)
        conflict_counts[j] += 1
    else:
      break

while 0 < max(conflict_counts):
  remove_robot_id = conflict_counts.index(max(conflict_counts))
  remove_robot = robots[remove_robot_id]
  remove_robot['removed'] = True
  for i in remove_robot['conflict_ids']:
    robots[i]['conflict_ids'].remove(remove_robot_id)
    conflict_counts[remove_robot_id] -= 1
    conflict_counts[i] -= 1

print(len(list(filter(lambda robot: not robot['removed'], robots))))

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()
    if len(b) > 0:
        if i[0]-i[1] <= max(b):
            #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
        else:
            b = []
            b.extend(list(range(i[0]-i[1], i[0]+i[1])))
    else:
        b.extend(list(range(i[0]-i[1], i[0]+i[1])))
        
    
print(n - count)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N= int(input())
ans = 1
a = []

for i in range(N):
    tmpa, tmpb = map(int,input().split())
    if tmpa-tmpb in a:
        a[tmpa-tmpb].append(tmpa+tmpb)
    else:
        a.append([tmpa-tmpb,tmpa+tmpb])

b = sorted(a, key=itemgetter(1))
tmp = b[0][1]
for i in range(1, N):
    if b[i][0] >= tmp:
        ans += 1
        tmp = b[i][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
j = 0
counter = 0

input_l = []

for i in range(num):
    a = input().split(" ")
    input_l.append(a)


for k in range(len(input_l)-1):
    for i in range(0, len(input_l) - 1 - k):
        if int(input_l[i][0]) > int(input_l[i+1][0]):
            x = input_l[i]
            input_l[i] = input_l[i+1]
            input_l[i+1] = x

while True:
    if j == len(input_l) - 1:
        break
    if (int(input_l[j][0]) + int(input_l[j][-1])) - (int(input_l[j+1][0]) - int(input_l[j+1][-1])) > 0:
        counter += 1
        del input_l[j+1]
    else:
        j += 1

print(num - counter)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[]
L=[]
XL=[]
for _ in range(N):
    XL.append(list(map(int,input().split())))
# まずかぶってる数の測定.まず中心座標でソート
XL.sort(key=lambda x: x[0])
# ２分木を使って何個かぶっているか判定する
import bisect
removed_num=0
while True:
    kaburi_list=[]
    max_ind=0
    max_kaburi=0
    for i,xl in enumerate(XL):
        x=[XL[j][0] for j in range(len(XL))]
        ind_left = bisect.bisect_left(x, xl[0]-xl[1])
        ind_right = bisect.bisect_right(x, xl[0]+xl[1])
        #自分は除くので
        kaburi = ind_right-1-ind_left
        kaburi_list.append(kaburi)
        if max_kaburi < kaburi:
            max_kaburi = kaburi
            max_ind=i
    if max_kaburi==0:
        print(N-removed_num)
        break
    else:
        max_ind = kaburi_list.index(max_kaburi)
        del XL[max_ind]
        removed_num+=1
            

# かぶっているやつ多いほど取り除いていく.

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)

R = [[X[n] - L[n], X[n] + L[n]] for n in range(N)]

R = sorted(R)
#print(R)

from bisect import bisect_right

rr = []

#print(rr)
s = []
sub = 0
ans = []
for x in range(N):
    
    for r in range(N):
        r += x
        if r >= N:
            r = r - N
        sIdx = bisect_right(s, R[r][0])
        eIdx = bisect_right(s, R[r][1])

        if sIdx == len(s) and eIdx == len(s):
            s.append(R[r][0])
            s.append(R[r][1])

        else:
            sub += 1

    ans.append(N - sub)
    #print(s)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

wide = [] # (left, right) 
for x, l in XL:
    wide.append((x-l, x+l))
wide.sort()

collisions = []
for idx, (l, r) in enumerate(wide):
    collisions.append([])
    for i in range(idx+1, N):
        if wide[i][0] < r:
            collisions[-1].append(i)
    for i in range(0, idx):
        if l < wide[i][1]:
            collisions[-1].append(i)
#print(wide)
#print(collisions)

collisions_num = []
collisions_sum = 0
for c in collisions:
    collisions_num.append(len(c))
    collisions_sum += len(c)

collisions_num.sort()
collisions_sum = collisions_sum // 2
#print(collisions_num)
#print(collisions_sum)
for i, n in enumerate(reversed(collisions_num)):
    if collisions_sum <= 0:
        print(N-i)
        break
    collisions_sum -= n

Submission status: Time Limit Exceeded

Solution code:
                
def getJufuku(xmin1,xmax1,l1,xmin2,xmax2,l2):
    ans = 0
    if xmax1 - xmin2 > 0 and xmax2 - xmin1 > 0:
        ans = xmax1 - xmin2
        if ans > xmax2 - xmin1:
            ans = xmax2 - xmin1
        if ans > l1*2:
            ans = l1*2
        if ans > l2*2:
            ans = l2*2
    return ans


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


while N > 1:
    cost = [0]*N
    for i in range(N):
        for j in range(N):
            if i < j:
                costmemo = getJufuku(Xmin[i],Xmax[i],L[i],Xmin[j],Xmax[j],L[j])
                cost[i] += costmemo
                cost[j] += costmemo
    delete = cost.index(max(cost))
    if cost[delete] == 0:
        break
    Xmin.pop(delete)
    Xmax.pop(delete)
    X.pop(delete)
    L.pop(delete)
    N -= 1

print(N)

Submission status: Time Limit Exceeded

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

if N == 1:
    print(1)
else:    
    i = 1
    while(len(move) > i):
        if move[i-1][0] == move[i][0]:
            if move[i-1][1] >= move[i][1]:
                del move[i]
            else:
                del move[i-1]
        else:
            if move[i][1] <= move[i-1][1]:
                del move[i]
            else:
                i += 1
    
    if len(move) <= 2:
        print(len(move))
    else:
        i = 1
        while(len(move) > i+1):
            if move[i-1][1] >= move[i+1][0]:
                del move[i]
            else:
                i += 1
        print(len(move))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N= int(input())
ans = 1
a = []

for i in range(N):
    tmpa, tmpb = map(int,input().split())
    if tmpa-tmpb in a:
        a[tmpa-tmpb].append(tmpa+tmpb)
    else:
        a.append([tmpa-tmpb,tmpa+tmpb])

a.sort(key=itemgetter(1))
tmp = a[0][1]
for i in range(1, N):
    if a[i][0] >= tmp:
        ans += 1
        tmp = a[i][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
arr = sorted(arr, key=lambda x: x[0])
F = [True]*N
P = [0]*N
for i in range(N):
  P[i] = [arr[i][0]-arr[i][1], arr[i][0]+arr[i][1]]
for i in range(N):
  for j in range(i+1,N):
    if F[i]:
      if P[i][1] > P[j][0]:
        F[j] = False
      elif P[i][1] <= P[j][0]:
        break
print(F.count(True))

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)

batting_count_list = []
batting_target_list = []
for i in range(len(X_list)):
  batting_count = 0
  batting_target = []
  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_target.append(j)
  batting_count_list.append(batting_count)
  batting_target_list.append(batting_target)

while True:
  max_batting_count = max(batting_count_list)
  if(max_batting_count != 0):
    max_index = batting_count_list.index(max_batting_count)
    for i in batting_target_list[max_index]:
      batting_count_list[i] -= 1
      batting_target_list[i].remove(max_index)
    X_list.pop(max_index)
    L_list.pop(max_index)
    batting_count_list.pop(max_index)
    batting_target_list.pop(max_index)
  else:
    break

print(len(X_list))

Submission status: Time Limit Exceeded

Solution code:
def getJufuku(xmin1,xmax1,l1,xmin2,xmax2,l2):
    ans = 0
    if xmax1 - xmin2 > 0 and xmax2 - xmin1 > 0:
        ans = xmax1 - xmin2
        if ans > xmax2 - xmin1:
            ans = xmax2 - xmin1
        if ans > l1*2:
            ans = l1*2
        if ans > l2*2:
            ans = l2*2
    return ans


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


while 1:
    cost = [0]*N
    for i in range(N):
        for j in range(N):
            if i < j:
                costmemo = getJufuku(Xmin[i],Xmax[i],L[i],Xmin[j],Xmax[j],L[j])
                cost[i] += costmemo
                cost[j] += costmemo
    delete = cost.index(max(cost))
    if cost[delete] == 0:
        break
    Xmin.pop(delete)
    Xmax.pop(delete)
    X.pop(delete)
    L.pop(delete)
    N -= 1

print(N)

Submission status: Time Limit Exceeded

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

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

t = list(map(lambda j:(j[0]-j[1]+1, j[0]+j[1]-1), s))
NN = len(t)
dobon = []

for k in range(NN):
  for l in range(k+1, NN):
    if l not in dobon:
      if int(t[k][1]) <= int(t[l][1]):
        if (t[l][0] <= t[k][1]) and (t[k][1] <= t[l][1]):
          N -= 1
          dobon.append(l)
          break
      else:
        if (t[l][0] <= t[k][0]) and (t[k][0] <= t[l][1]):
          N -= 1
          dobon.append(l)
          break

print(N)

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)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
 
N = 1
X = []
L = []
 
N = int(input())
for i in range(N):
    temp1, temp2 = input().split()
    X.append(int(temp1))
    L.append(int(temp2))
 
ans = N
ansFlag = True
ansTemp = 0
while True:
    if ans == 1:
        if ansTemp < ans:
            ansTemp = ans
        break
    for sets in list(itertools.combinations(range(N),ans)):
        ansFlag = True
        for pair in itertools.combinations(sets,2):
            if X[pair[0]] <= X[pair[1]]:
                if X[pair[0]] + L[pair[0]] > X[pair[1]] - L[pair[1]]:
                    ansFlag = False
                    break
            if X[pair[0]] >= X[pair[1]]:
                if X[pair[0]] - L[pair[0]] < X[pair[1]] + L[pair[1]]:
                    ansFlag = False
                    break
        else:
            if ansTemp < ans:
                ansTemp = ans
            break
    ans = ans-1
print(ansTemp)

Submission status: Time Limit Exceeded

Solution code:
class Robot:
    def __init__(self, x, l):
        self.l = l
        self.x = x
        self.left = x - l
        self.right = x + l
        self.contact_count = 0
        self.contact_index_list = []
        self.deleted = False

    def __repr__(self):
        return "<reprtest '%s' : '%s'>" % (self.x, self.l)


if __name__ == "__main__":
    N = int(input())

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

    while True:
        list_size = len(robot_list)
        for i in range(list_size):
            target = robot_list[i]
            for j in range(list_size):
                if i == j or target.deleted:
                    continue
                compare = robot_list[j]
                if not(target.right <= compare.left or target.left >= compare.right):
                    target.contact_count += 1
                    target.contact_index_list.append(j)

        # print('-----------')
        # print([robot for robot in robot_list])
        # print([robot.contact_count for robot in robot_list])
        # check = [robot.contact_count == 0 for robot in robot_list]
        # print(check)
        # print('-----------')
        if False in [robot.contact_count == 0 for robot in robot_list]:
            robot_list = sorted(robot_list, key=lambda x: x.contact_count)[:-1]
            for robot in robot_list:
                robot.contact_count = 0
        else:
            break

    print(len(robot_list))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
robot = [
    list(map(int, input().split())) for i in range(n)
]
robot.sort(key=lambda x: x[1])
ans = []
r_0 = robot.pop()
now = set(range(r_0[0]-r_0[1], r_0[0]+r_0[1]))
ans.append(r_0)

for i in range(1, n):
    robot_i = robot.pop()
    i_range = set(range(
        robot_i[0]-robot_i[1], robot_i[0]+robot_i[1]
    ))
    if len(now.intersection(i_range)) == 0:
        now = now.union(i_range)
        ans.append(robot_i)
print(len(ans))

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(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 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]], L[i]]

# 区間の長さが小さいものからみる
D.sort(key=lambda x:x[1])

ans = N
j = 0
while (j < len(D) - 1):
    k = j + 1
    while(k < len(D)):
        #print("now", D, "and j, k =", j, k)
        if have_common(D[j][0], D[k][0]):
            #print("remove", D[k])
            D.remove(D[k])
            ans -= 1
        k += 1
    j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
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())
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

not_accepted = []

for s in range(n):
    if max_cnt >= n - s + 1:
        break
    if s not in not_accepted and s > 0:
        continue

    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]:
            if s == 0:
                not_accepted.append(i)
            continue
        now_idx = i
        cnt += 1

    if max_cnt < cnt:
        max_cnt = cnt

print(max_cnt)

Submission status: Time Limit Exceeded

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

count = 0
count_b = 0
for j,k in enumerate(middle_list):
    if j == 0:
        for i in range(n):
            if min_list[i] <= k <= max_list[i]:
                count += 1
    else:
        for i in range(n):
            if min_list[i] <= k <= max_list[i]:
                count_b += 1
        count = max(count,count_b)
        count_b = 0
        
       
res = n - (count - 1)
    
print(res)

Submission status: Time Limit Exceeded

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

ans = 0
cnt = 0
li.sort()
temp = []

while True:
    arr = []
    check = -10**10
    if len(temp) == 0:
        for i in range(n):
            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:
        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]
    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())
result = n
min = []
max = []
for i in range(n):
    a,b = input().split()
    min.append(int(a) - int(b))
    max.append(int(a) + int(b))
    min.sort()
    max.sort()

tmp = 0
for i in range(n-1):
    if tmp == 1:
        tmp = 0
    elif max[i] > min[i+1]:
        result = result - 1
        tmp = 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
                
def getJufuku(xmin1,xmax1,l1,xmin2,xmax2,l2):
    ans = 0
    if xmax1 - xmin2 > 0 and xmax2 - xmin1 > 0:
        ans = xmax1 - xmin2
        if ans > xmax2 - xmin1:
            ans = xmax2 - xmin1
        if ans > l1*2:
            ans = l1*2
        if ans > l2*2:
            ans = l2*2
    return ans


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


while 1:
    cost = [0]*N
    for i in range(N):
        for j in range(N):
            if i < j:
                costmemo = getJufuku(Xmin[i],Xmax[i],L[i],Xmin[j],Xmax[j],L[j])
                cost[i] += costmemo
                cost[j] += costmemo
    delete = cost.index(max(cost))
    if cost[delete] == 0:
        break
    Xmin.pop(delete)
    Xmax.pop(delete)
    X.pop(delete)
    L.pop(delete)
    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.extend([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:
def delete_max_line(arr):
    max_i=0
    M=0
    i=0

    for a in arr:
        s=sum(a)
        if M<s:
            M=s
            max_i=i
        i+=1

    arr.pop(max_i)
    for a in arr:
        a.pop(max_i)

    return M

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

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

XL.sort()

attach=[[0]*N for i in range(N) ]

right=[xl[0]+xl[1] for xl in XL]
left=[xl[0]-xl[1] for xl in XL]

for i in range(N-1):
    for j in range(i+1,N):
        if right[i]>left[j]:
            attach[i][j]=1
            attach[j][i]=1

ans=0
while True:
    judge=delete_max_line(attach)
    if judge==0:
        break
    ans+=1

    

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
dict_area = {}
max_count = 0
for i in range(0, n):
    x, l = map(int, input().split())
    start = x - l + 1
    if x - l + 1 < 0:
        start = 0
    end = x + l
    if end > 10 ** 9:
        end = 10 ** 9
    for j in range(start, end):
        if j in dict_area:
            dict_area[j] += 1
            if max_count < dict_area[j] - 1:
                max_count = dict_area[j] - 1
        else:
            dict_area[j] = 1
print(n - max_count)

Submission status: Time Limit Exceeded

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

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:
N = int(input())
A_list = [input().split() for _ in range(N)]

ans = []
before_count = 0


def has_duplicates(seq):
    return len(seq) != len(set(seq))


def open(list):
    retval = [int(list[0])]
    for i in range(1, int(list[1])):
        retval.append(int(list[0]) + i)
        retval.append(int(list[0]) - i)
    return retval


# list = open(A_list[0]) + open(A_list[1])
#
# print(list)

for i in range(2 ** len(A_list)):
    ans = []
    count = 0
    for j in range(len(A_list)):
        if (i >> j) & 1:
            count += 1  # 使用している個数
            ans += open(A_list[len(A_list) - 1 - j])

    if not has_duplicates(ans):
        if count > before_count:
            before_count = count

print(before_count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = []
L = []
for i in range(N):
  line = input().split(' ')
  t1 = int(line[0])
  t2 = int(line[1])
  for j in range(i):
    if X[j] > t1:
      X.insert(j,t1)
      L.insert(j,t2)
      break
    elif j == i - 1:
      X.append(t1)
      L.append(t2)
  if i == 0:
    X.append(t1)
    L.append(t2)
i = 0
t1 = len(X)
t2 = 0
while i < t1 - t2 - 1:
  j = i+1
  while j < t1-t2:
    if X[i] + L[i] > X[j] - L[j]:
      X.pop(j)
      L.pop(j)
      t2 += 1
    j+=1
  i+=1
print(len(X))

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[1])

cnt = [0 for _ in range(10**8)]
ans = [0 for _ in range(n)]

for i in range(n):
    for j in range(xl[i][0] - xl[i][1] + 1, xl[i][0] + xl[i][1]):
        if cnt[j] == 0:
            cnt[j] = 1
        else:
            break
        if j == xl[i][0] + xl[i][1]-1:
            ans[i] = 1

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
line = []

x, l = map(int, input().split())
ans = 1
for i in range(x-l+1, x+l):
  line.append(i)
 
for i in range(n-1):
  x, l = map(int, input().split())
  keep = True
  if (x - l + 1 <= min(line)) and (x + l - 1 >= min(line)):
    keep = False
  elif (x - l + 1 <= max(line)) and (x + l - 1 >= max(line)):
    keep = False
  else:
    for j in range (x-l+1, x+l):
      if j in line:
        keep = False

  if keep == True:
    ans += 1
    for i in range(x-l+1, x+l):
      line.append(i)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
s=[list(map(int,input().split())) for i in range(N)]
A=N
c=0
s.sort(key=lambda x: x[0])

Check=[[s[i][0]-s[i][1],s[i][0]+s[i][1]] 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:
def main():
    n = int(input())

    s = []
    e = []
    tls = []
    buff = {}
    for i in range(n):
        tmp = list(map(int, input().split()))
        s.append(tmp[0] - tmp[1])
        e.append(tmp[0] + tmp[1])
    for i in range(n):
        buff[s[i]] = e[i]
    
    maxcount = 0
    sorted_s = sorted(s)
    preve = 0
    while len(sorted_s) > 0:
        tmps = sorted_s[0]
        tmpe = buff[tmps]
        if preve == 0:
            maxcount += 1
            preve = tmpe
            sorted_s = sorted_s[1:]
        elif tmps >= preve:
            maxcount += 1
            preve = tmpe
            sorted_s = sorted_s[1:]
        elif tmpe < preve:
            preve = tmpe
            sorted_s = sorted_s[1:]
        else:
            sorted_s = sorted_s[1:]
    print(maxcount)
    return
if __name__ == "__main__":
    main()

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()
    if len(b) > 0:
        if i[0]-i[1] <= max(b):
            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
        else:
            b = []
            b.extend(list(range(i[0]-i[1], i[0]+i[1])))
    else:
        b.extend(list(range(i[0]-i[1], i[0]+i[1])))
        
    
print(n - count)