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())
X = []; L = []
for _ in range(N):
    X_tmp, L_tmp = [int(x) for x in input().split()]
    X.append(X_tmp)
    L.append(L_tmp)

dup = {}
for i in range(N - 1):
    for j in range(i + 1, N):
        if X[i] - L[i] < X[j] + L[j] and X[i] + L[i] > X[j] - L[j]:
            if i in dup:
                dup[i].append(j)
            else:
                dup[i] = [j]
            if j in dup:
                dup[j].append(i)
            else:
                dup[j] = [i]

size_max = 0
for i in dup:
    size_max = max(len(dup[i]), size_max)

size = {}
for i in range(size_max):
    size[i + 1] = []

for i in dup:
    size[len(dup[i])].append(i)

ans = 0
while len(dup) > 0:
    t = size[max(size.keys())][0]
    for s in dup[t]:
        if len(dup[s]) == 1:
            size[1].remove(s)
            del dup[s]
        else:
            size[len(dup[s])].remove(s)
            size[len(dup[s]) - 1].append(s)
            dup[s].remove(t)
    size[len(dup[t])].remove(t)
    del dup[t]
    ans += 1
ans = N - ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
alllist = []
remain = 0
for i in range(N):
    X, L = map(int,input().split())
    alllist.append([i for i in range(X-L,X+L)])
d = 0
l = alllist
for i in range(N):
    kumiawase = N-i
    c_list = list(itertools.combinations(l, kumiawase))
    for j in range(len(c_list)):
        first = c_list[j][0]
        c= 1
        for k in range(len(c_list[j])-1):
            if len(set(c_list[j][k+1]) & set(first)) == 0:
                c += 1
            else:
                break
        if c == kumiawase:
            print(kumiawase)
            d = 1
            break
        else:
            pass
    if d == 1:
        break
    else:
        pass

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
l = []
x = 0
y = 0
count = 1

for i in range(n):
    x,y = map(int,input().split())
    l.append([x,y])
    l.sort()
#print(l)

r = l[0][0] + l[0][1]
#print(r)

for i in range(0,n-1):
#    print(l[i+1][0] - l[i+1][1])
    if r <= l[i+1][0] - l[i+1][1]:
        r = l[i+1][0] + l[i+1][1]
        count += 1
#        print(r)
    else:
        pass

if r <= l[-1][0] - l[-1][1]:
    count += 1
else:
    pass

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF=10 ** 10
N = int(input())
XL = sorted([list(map(int,input().split())) for _ in range(N)])
# print(N,XL)

DP = [ INF for _ in range(N+1)]
DP[0] = -INF
for i in range(N):
    #print(DP)
    (x,l) = XL[i]
    # print(x,l)
    for j in range(1,N+1):
        if DP[j-1] > x -l:
            break
        if ( DP[j-1]<= x -l and x + l < DP[j]):
                DP[j] = x + l
#print(DP)
for i in range(2,N+1):
    if DP[i] == INF:
        print(i-1)
        exit(0)
print(N)

Submission status: Time Limit Exceeded

Solution code:
# coding utf-8
n_robot = int(input())
robot_data = []
for i in range(n_robot):
    datum = [int(x) for x in input().split()]
    robot_data.append({'number': i,'position_min': datum[0] - datum[1], 'position_max': datum[0] + datum[1], 'duplication': 0, 'duplication_target': [], "deleated": False})

for i in range(n_robot-1):
    for j in range(i+1, n_robot):
        if (robot_data[i]['position_min'] < robot_data[j]['position_min'] and robot_data[i]['position_max'] > robot_data[j]['position_min'])\
        or (robot_data[i]['position_min'] < robot_data[j]['position_max'] and robot_data[i]['position_max'] > robot_data[j]['position_max'])\
        or (robot_data[i]['position_min'] > robot_data[j]['position_min'] and robot_data[i]['position_max'] < robot_data[j]['position_max']):
            robot_data[i]['duplication'] += 1
            robot_data[i]['duplication_target'].append(j)
            robot_data[j]['duplication'] += 1
            robot_data[j]['duplication_target'].append(i)
           
deleated_count = 0
while True:
    max_duplicated_robonum = max(robot_data, key=lambda x: x['duplication'])['number']
    if robot_data[max_duplicated_robonum]['duplication'] == 0:
        break
    else:
        for target_num in robot_data[max_duplicated_robonum]['duplication_target']:
            robot_data[target_num]['duplication'] -= 1
            robot_data[target_num]['duplication_target'].remove(max_duplicated_robonum)
        robot_data[max_duplicated_robonum]['deleated'] = True
        robot_data[max_duplicated_robonum]['duplication'] = 0
        deleated_count += 1

print(n_robot - deleated_count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
lis = [[0,0] for _ in range(N)]
X = [0 for _ in range(N)]
ans = []
for i in range(N):
    x,l = map(int, input().split(" "))
    lis[i] = (x-l,x+l)
    X[i] = x
s = []
ans_append = ans.append
s_append = s.append
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())
XL = [list(map(int, input().split())) for i in range(N)]

maxJ = 0
maxL = 0
flag = False
count = 0
for i in range(N):
    #print("+++++++" + str(i),i-count, XL )
    i = i-count
    maxL = XL[i][1]
    flag = False
    for j in range(i+1, len(XL)):
        #print("+" + str(j) )
        if XL[i][0]+XL[i][1] > XL[j][0]-XL[j][1]:
            if XL[j][1] > maxL:
                #print("++" + str(j) )
                maxL = XL[j][1]
                maxJ = j
                flag = True
        else:
            break
    if i > 0:
        for j in range(i-1, -1, -1):
            #print("-" + str(j) )
            if XL[i][0]-XL[i][1] < XL[j][0]+XL[j][1]:
                if XL[j][1] > maxL: 
                    #print("--" + str(j) )
                    maxL = XL[j][1]
                    maxJ = j
                    flag = True
            else:
                break
    if flag:
        del(XL[maxJ])
        count += 1


print(len(XL))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[]
L=[]
for i in range(N):
    x,l=map(int,input().split())
    X.append(x)
    L.append(l)
restart=True
while restart:
    v=[0]*len(X)
    for i in range(len(X)):
        count=0
        a=X[i]+L[i]
        b=X[i]-L[i]
        for j in range(i+1,len(X)):
            c=X[j]+L[j]
            d=X[j]-L[j]
            if (d<a and a<c) or (d<b and b<c) or (b<d and c<a) or (d<b and a<c):
                v[i]+=1
                v[j]+=1
                if v[i]>1:
                    X.pop(i)
                    L.pop(i)
                    break
                if v[j]>1:
                    X.pop(j)
                    L.pop(j)
                    break

        else:

            continue

        break
    else:
        restart=False
c=v.count(1)

print(int(len(X)-c/2))

Submission status: Time Limit Exceeded

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


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


def main():
    N = int(input())
    X, L, D = [0] * N, [0] * N, [0] * N
    D_remove = D.remove
    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)):
            if have_common(D[j][0], D[k][0]):
                D_remove(D[k])
                ans -= 1
            k += 1
        j += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF=10 ** 10
N = int(input())
XL = sorted([list(map(int,input().split())) for _ in range(N)])
# print(N,XL)

DP = [ INF for _ in range(N+1)]
DP[0] = -INF
for i in range(N):
    #print(DP)
    (x,l) = XL[i]
    # print(x,l)
    for j in range(1,N+1):
        if DP[j-1] > x -l:
            continue
        if ( DP[j-1]<= x -l and x + l < DP[j]):
                DP[j] = x + l
#print(DP)
for i in range(2,N+1):
    if DP[i] == INF:
        print(i-1)
        exit(0)
print(N)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
sys.setrecursionlimit(10**9)

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

robots = [[X[i]-L[i], X[i]+L[i]] for i in range(N)]
robots = sorted(robots, key=lambda x: x[1])
robots = sorted(robots, key=lambda x: x[0])

max_record = 0
right_max_dict = {robot[1]: None for robot in robots}


def rec(idx, right, n_robot, used):
    global max_record

    if idx == N:
        if n_robot > max_record:
            max_record = n_robot
        return None

    if used:
        old_right = right_max_dict[robots[idx][1]]
        if old_right is None:
            right_max_dict[robots[idx][1]] = n_robot
        else:
            if old_right >= n_robot:
                return None

    if right <= robots[idx][0]:
        rec(idx+1, robots[idx][1], n_robot+1, True)  # idx番目を使う
        rec(idx+1, right, n_robot, False)  # idx番目を使わない
    else:
        rec(idx+1, right, n_robot, False)  # idx番目を使わない


rec(0, -(10**9), 0, False)

print(max_record)

Submission status: Time Limit Exceeded

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

l = [r[0]]
r = r[1:]
while len(r) > 0:
    x1, l1 = l[-1]
    x2, l2 = r[0]
    if (x1+l1) > (x2-l2):
        if (x1+l1) > (x2+l2):
            l.pop()
            l.append(r[0])
            r.pop(0)
        else:
            r.pop(0)
    else:
        l.append(r[0])
        r.pop(0)
print(len(l))

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect_left

def resolve():
    N = int(input())
    #S = [list(iim()) for i in range(N)]
    MX = 10**9
    S = []
    for i in range(N):
        x, l = iim()
        i = x - l
        if i < 0:
            i = 0
        j = x + l
        if j > MX:
            j = MX

        a = [i, j]
        S.append(a)
    S.sort()

    d = dict()
    x, y = S[0]
    d = {-1: 0}
    dk = [-1]
    ans = 0
    for x, y in S:
        for xx in dk:
            if xx <= x:
                n = d[xx] + 1
                if y in d:
                    if d[y] < n:
                        d[y] = n
                        if ans < n:
                            ans = n
                else:
                    d[y] = n
                    dk.append(y)
                    if ans < n:
                        ans = n
        #print(x, y, d)
    print(n)






if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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


result2 = 0
a = 0
if list_1[0][1] != 0:
    result2 += 1
    a = list_1[0][0] + list_1[0][1]
try:
    for j in range(len(list_1)):
        if list_1[j][0] == list_1[j][1] and list_1[j][0] == 0 and list_1[j][0] == list_1[j + 1][0]:
            None
        elif list_1[j][0] == list_1[j][1] and list_1[j][0] == 0 and list_1[j][0] != list_1[j + 1][0]:
            result2 += 1
            a = list_1[j + 1][0] + list_1[j + 1][1]
            #print("2716")
        elif a <= list_1[j][0] - list_1[j][1]:
            #print("!!!!!!!")
            result2 += 1
            a = list_1[j][0] - list_1[j][1]
except:
    None

list_1.sort(key=lambda x: x[1])
#print(list_1)
result = 0
lists = []
for j in range(len(list_1)):
    x = list(set(lists) & set(list(range(list_1[j][0]-list_1[j][1],list_1[j][0]+list_1[j][1]))))
    if list_1[j][0] == list_1[j][1] and list_1[j][0] == 0 :
        None
    elif len(x) == 0 :
        lists += list(range(list_1[j][0]-list_1[j][1],list_1[j][0]+list_1[j][1]))
        result += 1
    elif len(x) == 2:
        if min(x) == list_1[j][0]-list_1[j][1] and max(x) ==list_1[j][0]+list_1[j][1]:
            lists += list(range(list_1[j][0] - list_1[j][1], list_1[j][0] + list_1[j][1]))
            result += 1

print(max(result,result2))

Submission status: Time Limit Exceeded

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

robots.sort(key=lambda hw: hw[0])



collision= {i: [] for i in range(n)}
for i, (hi, wi) in enumerate(robots):
  right = hi + wi
  for k, (hj, wj) in enumerate(robots[i+1:]):
    if hj - wj < right:
      collision[i].append(i + k + 1)
      collision[i + k + 1].append(i)
    else:
      break

removed = 0
for i in range(n):
  if not collision[i]:
    del collision[i]
while(collision):
  k, v = sorted(list(collision.items()), key=lambda x: len(x[1]), reverse=True)[0]
  removed += 1
  del collision[k]
  keys = list(collision.keys())
  for k2 in keys:
    if k in collision[k2]:
      collision[k2].remove(k)
      if not collision[k2]:
        del collision[k2]

print(n - removed)

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 ansTemp == 0:
    for sets in list(itertools.combinations(range(N),ans)):
        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]]:
                    break
            if X[pair[0]] >= X[pair[1]]:
                if X[pair[0]] - L[pair[0]] < X[pair[1]] + L[pair[1]]:
                    break
        else:
            ansTemp = ans
            break
    ans = ans-1
print(ansTemp)

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pdb
import sys
F = sys.stdin

N = int(F.readline().rstrip())
x_list = []
x_l_dict = {}
x_lmin_dict = {}
x_lmax_dict = {}
x_weight = {}

for n in range(N):
    x1, l1 = map(int,F.readline().split())
    x_list.append(x1)
    x_l_dict[x1] = l1
    x_lmin_dict[x1] = x1 - l1
    x_lmax_dict[x1] = x1 + l1
    x_weight[x1] = 0

x_list.sort()
for index in range(len(x_list)):
    if index != 0:
        x = x_list[index]
        for m in range(index):
            x_test = x_list[m]
            if x_lmin_dict[x] < x_lmax_dict[x_test]:
                x_weight[x] += 1

    if index != len(x_list) - 1:
        x = x_list[index]
        for m in range(index + 1, len(x_list)):
            x_test = x_list[m]
            if x_lmax_dict[x] > x_lmin_dict[x_test]:
                x_weight[x] += 1



for i in range(len(x_list) - 1):
    x = x_list[i]
    if x not in x_l_dict :
        continue
    for j in range(i+1, len(x_list)):
        x_test = x_list[j]
        if x_lmax_dict[x] > x_lmin_dict[x_test]:
            if x_weight[x] > x_weight[x_test]:
                x_l_dict.pop(x)
                continue
            if x_weight[x] <= x_weight[x_test]:
                x_l_dict.pop(x_test)

ans = len(x_l_dict)



print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding utf-8
n_robot = int(input())
robot_data = []
for i in range(n_robot):
    datum = [int(x) for x in input().split()]
    robot_data.append({'number': i,'position': datum[0], 'position_min': datum[0] - datum[1], 'position_max': datum[0] + datum[1], 'duplication': 0, 'duplication_target': [], "deleated": False})

for i in range(n_robot-1):
    for j in range(i+1, n_robot):
        if (robot_data[i]['position_min'] < robot_data[j]['position_min'] and robot_data[i]['position_max'] > robot_data[j]['position_min'])\
        or (robot_data[i]['position_min'] < robot_data[j]['position_max'] and robot_data[i]['position_max'] > robot_data[j]['position_max'])\
        or (robot_data[i]['position_min'] > robot_data[j]['position_min'] and robot_data[i]['position_max'] < robot_data[j]['position_max']):
            robot_data[i]['duplication'] += 1
            robot_data[i]['duplication_target'].append(j)
            robot_data[j]['duplication'] += 1
            robot_data[j]['duplication_target'].append(i)
           
            
while True:
    max_duplicated_robonum = max(robot_data, key=lambda x: x['duplication'])['number']
    if robot_data[max_duplicated_robonum]['duplication'] == 0:
        break
    else:
        for target_num in robot_data[max_duplicated_robonum]['duplication_target']:
            robot_data[target_num]['duplication'] -= 1
            robot_data[target_num]['duplication_target'].remove(max_duplicated_robonum)
        robot_data[max_duplicated_robonum]['deleated'] = True
        robot_data[max_duplicated_robonum]['duplication'] = 0
        
        
count = 0
for x in robot_data:
    if x['deleated'] == False:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:

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

newflag=-(-flag//2)
print(N-newflag)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
li=[]
for i in range(n):
  tmpli=list(map(int, input().split()))
  li.append(tmpli)
li.sort()
# print(li)
for i in range(len(li)-1):
  if li[i][0]+li[i][1] > li[i+1][0]-li[i+1][1]:
    li[i+1][0] = 0
    li.sort()
    n -= 1
print(n)

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)
            X.pop(i)
            i -= 1
        else:
            d.pop(x_1)
            X.pop(i-1)
            i -= 1

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

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]

cost = [0]*N
cost_mat = [[0]]*N
for i in range(N):
    cost_mat[i] = [0] * 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
            cost_mat[i][j] = costmemo

ans = N
while ans > 1:
    i = cost.index(max(cost))
    if cost[i] == 0:
        break
    for j in range(N):
        if i < j:
            cost[i] -= cost_mat[i][j]
            cost[j] -= cost_mat[i][j]
            cost_mat[i][j] = 0
        if j < i:
            cost[i] -= cost_mat[j][i]
            cost[j] -= cost_mat[j][i]
            cost_mat[j][i] = 0
    ans -= 1

print(ans)

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:
            del d[x_2]
            X.pop(i)
            i -= 1
        else:
            del d[x_1]
            X.pop(i-1)
            i -= 1

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

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    inputs = [input().split() for i in range(n)]
    inputs_list = []
    for tmp in inputs:
        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())
list_1 = [list(map(int,input().split())) for i in range(N)]
list_1.sort()
#print(list_1)
for i in range(N-1):
    if list_1[i][0] == list_1[i+1][0]:
        if list_1[i][1] >= list_1[i+1][1]:
            list_1[i] = [0,0]
        else:
            list_1[i+1] = [0,0]
    else:
        None

result2 = 0
a = 0
if list_1[0][1] != 0:
    result2 += 1
    a = list_1[0][0] + list_1[0][1]
try:
    for j in range(len(list_1)):
        if list_1[j][0] == list_1[j][1] and list_1[j][0] == 0 and list_1[j][0] == list_1[j + 1][0]:
            None
        elif list_1[j][0] == list_1[j][1] and list_1[j][0] == 0 and list_1[j][0] != list_1[j + 1][0]:
            result2 += 1
            a = list_1[j + 1][0] + list_1[j + 1][1]
            #print("2716")
        elif a <= list_1[j][0] - list_1[j][1]:
            #print("!!!!!!!")
            result2 += 1
            a = list_1[j][0] - list_1[j][1]
except:
    None

list_1.sort(key=lambda x: x[1])
#print(list_1)
result = 0
lists = []
for j in range(len(list_1)):
    x = list(set(lists) & set(list(range(list_1[j][0]-list_1[j][1],list_1[j][0]+list_1[j][1]))))
    if list_1[j][0] == list_1[j][1] and list_1[j][0] == 0 :
        None
    elif len(x) == 0 :
        lists += list(range(list_1[j][0]-list_1[j][1],list_1[j][0]+list_1[j][1]))
        result += 1
    elif len(x) == 2:
        x.sort()
        if x[0] == list_1[j][0]-list_1[j][1] and x[1] ==list_1[j][0]+list_1[j][1]:
            lists += list(range(list_1[j][0] - list_1[j][1], list_1[j][0] + list_1[j][1]))
            result += 1




print(max(result,result2))

Submission status: Time Limit Exceeded

Solution code:
class Robot:
    def __init__(self, index, x, l):
        self.index = index
        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(i, x, l))

    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('-----------')
    delete_count = 0
    while False in [robot.contact_count == 0 for robot in robot_list]:
        # robot_list = sorted(robot_list, key=lambda x: x.contact_count)
        max_robot = max(robot_list, key=lambda x: x.contact_count)
        max_robot.contact_count = 0
        for i in max_robot.contact_index_list:
            if (robot_list[i].contact_count >= 1):
                robot_list[i].contact_count -= 1
        delete_count += 1

    print(len(robot_list) - delete_count)

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 = sorted(move, key=lambda x:(x[0],x[1]))

if N == 1:
    print(1)
else:    
    i = 1
    while(len(move) > i):
        if move[i-1][0] == move[i][0]:
            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:
def search_delete(data):
    del_target = -1
    max_count = 1
    for i in range(len(data)):
        count = 0
        for j in range(i+1, len(data)):
            if data[i][1] > data[j][0]:
                count += 1
            else:
                break
        if count >= max_count:
            del_target = i
            max_count = count
    if del_target != -1:
        data.pop(del_target)
        return True
    return False


def main():
    n = int(input())
    data = []
    for i in range(n):
        x, l = map(int, input().split())
        data.append([x-l, x+l])
    data.sort(key=lambda x: x[0])

    remove = []
    for i in range(len(data)-1):
        if data[i][1] < data[i+1][0]:
            remove.append(data[i])

    for x in remove[:]:
        data.remove(x)

    flg = True
    while flg:
        flg = search_delete(data)

    print(len(remove)+len(data))


main()

Submission status: Time Limit Exceeded

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

hidari_arr = [0] * N
for i in range(len(List)):
  a = List[i][0]
  b = List[i][1]
  c = a-b
  hidari_arr[i] = c
  
migi_arr = [0] * N
for i in range(len(List)):
  a = List[i][0]
  b = List[i][1]
  c = a+b
  hidari_arr[i] = c

for i in range(len(List)-2):
  migi = int(List[i][0] + List[i][1])
  if hidari_arr[i+2:len(List)-1] != []:
    hidari = min(hidari_arr[i+2:len(List)-1])
    if migi > hidari:
      List[i][0] = -10000000000
      List[i][1] = 0
      cnt = cnt + 1
List.sort()

length = len(List)-1
for i in range(len(List)-2):
  if i > 1:
    if migi_arr[0:length-(i+2)] != []:
      migi = max(migi_arr[0:length-(i+2)])
      hidari = int(List[length-i][0] - List[length-i][1])
      if migi > hidari:
        List[length-i][0] = 90000000000
        List[length-i][1] = 0
        cnt = cnt + 1
List.sort()
for i in range(len(List)-1):
  if i > 0:
    hidari_1 = int(List[i][0] - List[i][1])
    migi_1 = int(List[i-1][0] + List[i-1][1])

    migi_2 = int(List[i][0] + List[i][1])
    hidari_2 = int(List[i+1][0] - List[i+1][1])
    
    if hidari_1 < migi_1 and migi_2 > hidari_2:
      List[i][0] = -10000000000
      List[i][1] = 0
      cnt = cnt + 1
List.sort()
for i in range(len(List)-1):
  hidari = int(List[i+1][0] - List[i+1][1])
  migi = int(List[i][0] + List[i][1])
  if hidari < migi:
    List[i][0] = -10000000000
    List[i][1] = 0
    cnt = cnt + 1

print(N-cnt)

Submission status: Time Limit Exceeded

Solution code:
import statistics


def main():
    N = int(input())
    robots = list()
    hit_cnt = list()
    hits = 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)
                hits.append(n)
                hits.append(i)

    while len(hits) > 0:
        try:
            del_index = statistics.mode(hits)
        except:
            del_index = 0
            for i in hits:
                if del_index < hits.count(i):
                    del_index = i

        hits = [hit for hit in hits if hit != del_index]
        for i in hit_cnt[del_index]:
            hits.remove(i)
        robots.pop(del_index)
    print(len(robots))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0]*n
s = 0
d = {}
for i in range(n):
  x,l = map(int, input().split())
  if i != 0:
    for j in range(i):
      if d[j][0]-d[j][1]<x+l and x-l<d[j][0]+d[j][1]:
        a[j]+=1
        a[i]+=1
        s+=1
  d[i] = (x,l)
a.sort(reverse=True)
ans_=0
while(s>0):
  s -= a[ans_]*2
  ans_ += 1
print(n-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)
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
      else:
        break
print(F.count(True))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
robots = [[int(i) for i in input().split()] for i in range(n)]

min_sub = 1000
flag = 0

for i in range(n):

    robot = robots[i]
    arm = (robot[0] - robot[1], robot[0] + robot[1])
    sub = 0
    for j in range(n):

        if i == j:
            continue
        else:
            robot = robots[j]
            n_arm =  (robot[0] - robot[1], robot[0] + robot[1])

            if arm[1] > n_arm[0] and arm[0] < n_arm[0]:
                sub += 1
                #print("arm", arm)
                #print("n_arm", n_arm)
                flag = 1
            elif arm[0] > n_arm[0] and arm[0] < n_arm[1]:
                sub += 1
                #print("arm", arm)
                #print("n_arm", n_arm)
                flag = 1
    if sub != 0:
        min_sub = min(min_sub, sub)

if flag == 0:
    print(n)
else:
    print(n - min_sub)