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())

start = []
is_left = [True for i in range(n)]
length = []

for _ in range(n):
    x, l = map(int,input().split())
    start.append(x+l)
    length.append(l)

sorted_length = []
length.sort(key= lambda x: start)
start_i = [i for i in range(n)]
start_i.sort(key=lambda x:start[x])
start.sort()
for i in start_i:
    sorted_length.append(length[i])


for i in range(1,n):
    if start[i] - (2*sorted_length[i]) < start[i-1]:
        if is_left[i-1] == True:
            is_left[i] = False

print(sum(is_left))

Submission status: Time Limit Exceeded

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

p = []

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(0))



for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(0))
  else:
    p.pop(0)

print(len(ex))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
X, L = np.zeros(N), np.zeros(N)

for i in range(N):
    x, l = list(map(int, input().split()))
    X[i] = x
    L[i] = l
right_end = X + L
left_end = X - L
sorted_ind = np.argsort(right_end)

cur = int(-1e10)
cnt = 0
for i in range(N):
    if left_end[sorted_ind][i] >= cur:
        cur = right_end[sorted_ind][i]
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
numbers=[]
for _ in range(N):
    X,L=map(int,input().split())
    left=X-L
    right=X+L
    numbers.append([right,left])
numbers=sorted(numbers)
answer=1
large=numbers[0][0]
for  _ in range(len(numbers)-1):
    if numbers[answer][0]>large and numbers[answer][1]>=large:
        large=numbers[answer][0]
        answer+=1
    else:
        del numbers[answer]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
numbers=[]
for _ in range(N):
    X,L=map(int,input().split())
    left=X-L
    right=X+L
    numbers.append([right,left])
numbers=sorted(numbers)
answer=1
for  _ in range(len(numbers)-1):
    if numbers[answer][0]>numbers[answer-1][0] and numbers[answer][1]>=numbers[answer-1][0]:
        answer+=1
    else:
        del numbers[answer]
print(answer)

Submission status: Time Limit Exceeded

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

rXL = []
for i, j in XL:
    rXL.append([i - j, i + j])
rXL = sorted(rXL, key = lambda x: x[1])
TF = [True for _ in range(N)]

for i in range(1, N):
    for j in range(i):
        if rXL[i][0] < rXL[j][1] and rXL[i][1] > rXL[j][0] and TF[j]:
            TF[i] = False

print(sum(TF))

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] = map(int, input().split())

start = -1000000000
seen = [False]*N

while True:
    min = 2000000000
    minin = None
    for i in range(N):
        if X[i]-L[i]< start or seen[i]==True:continue
        if X[i]+L[i]<min:
            min = X[i]+L[i]
            minin = i

    if minin == None:
        break
    seen[minin] = True
    start = min

print(seen.count(True))

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
xl = []
for i in range(n):
    xl.append([int(i) for i in input().split()])
    xl[i].append(xl[i][0] - xl[i][1])
    xl[i].append(xl[i][0] + xl[i][1])
xl.sort(key=lambda x: x[3])
ng = []
ans = 0
for i in range(n):
    tmp = list(range(xl[i][2] + 1, xl[i][3]))
    a = copy.deepcopy(tmp) #動く範囲
    a.extend(ng)
    if len(set(a)) == len(a):
        ng.extend(tmp)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in l:
    x = 0 if i[0]-i[1] < 0 else i[0]-i[1]
    i[1] = i[0]+i[1]
    i[0] = x
    
l.sort(key=lambda x:x[1])

while l:
    cnt+=1
    x = l.pop(0)
    delete = []
    for i in range(len(l)):
        if x[1] > l[i][0]:
            delete.append(i)

    for i in range(len(delete)):
        l.pop(delete[i]-i)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
T=[]
for i in range(N):
    X,L=map(int,list(input().split(" ")))
    T.append([X+L,X-L])
T.sort()
sum=1
def check(T,v,w):
    if T[v][0]<=T[w][1] or T[v][1]>=T[w][0]:
        return True
    else:
        return False

checks=[0]
for i in range(1,N):
    count=0
    for  j in checks:
        if not check(T,i,j):
            break
        count+=1
    if count==len(checks):
        sum+=1
        checks.append(i)
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
X=[]
x=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append([a+b,a-b])

def nibun(lis,x):
    i=len(lis)
    if i==1:
        if lis[0]<=x:
            return lis[0]
    elif lis[i//2]==x:
        return x
    else:
        if x<lis[i//2]:
            return nibun(lis[:i//2],x)
        else:
            return nibun(lis[i//2:],x)
X.sort()
a={}
a[X[0][0]]=1
a[-np.inf]=0
T=[]
b={}
for i in range(1,N):
    T.append(X[i-1][0])
    k=nibun(T,X[i][1])
    if k==None:
        b[i]=-np.inf
    else:
        b[i]=k
    a[X[i][0]]=max(a[X[i-1][0]],a[b[i]]+1)
print(a[X[N-1][0]])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[]
x=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append(a+b)
    x.append(a-b)

def nibun(lis,x):
    i=len(lis)
    if i==1:
        if lis[0]<=x:
            return lis[0]
    elif lis[i//2]==x:
        return x
    else:
        if x<lis[i//2]:
            return nibun(lis[:i//2],x)
        else:
            return nibun(lis[i//2:],x)

X.sort()
x.sort()
a={}
a[x[0]]=0
a[X[0]]=1
for i in range(1,N):
    k=nibun(X[:i],x[i])
    if k==None:
        a[x[i]]=0
    else:
        a[x[i]]=a[k]
    a[X[i]]=max(a[X[i-1]],a[x[i]]+1)
print(a[X[N-1]])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[]
x=[]
for i in range(N):
    a,b=map(int,list(input().split(" ")))
    X.append(a+b)
    x.append(a-b)

def nibun(lis,x):
    i=len(lis)
    if i==1:
        if lis[0]<=x:
            return lis[0]
    elif lis[i//2]==x:
        return x
    else:
        if x<lis[i//2]:
            return nibun(lis[:i//2],x)
        else:
            return nibun(lis[i//2:],x)
    
X.sort()
x.sort()
a={}
a[x[0]]=0
a[X[0]]=1
for i in range(1,N):
    if nibun(X,x[i])==None:
        a[x[i]]=0
    else:
        a[x[i]]=a[nibun(X,x[i])]
    a[X[i]]=max(a[X[i-1]],a[x[i]]+1)
print(a[X[N-1]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
robot_list = []
for i in range(N):
  robot_list.append(list(map(int, input().split())))

def choose_coordinate(now_edge):
  global robot_list
  global res
  next_edge = pow(10, 10)

  for i in range(N):
    robot_right_edge = robot_list[i][0] + robot_list[i][1]
    robot_left_edge = robot_list[i][0] - robot_list[i][1]
    if robot_left_edge >= now_edge and robot_right_edge <= next_edge:
      next_edge = robot_right_edge
    
  if next_edge == pow(10, 10):
    return
  else:
    res += 1
    choose_coordinate(next_edge)

res = 0
choose_coordinate(- pow(10,10))

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = [0]*N
L = [0]*N
XpL = [0]*N
XmL = [0]*N
cnt = 0
for i in range(N):
    X[i], L[i] = map(int, input().split())
    XpL[i] = X[i]+L[i]
    XmL[i] = max(0, X[i]-L[i])
    
    for j in range(i):
        if(XmL[i] < XpL[j] and XmL[j] < XpL[i]):
            cnt += 1
            XpL[i] = XpL[j]
            XmL[i] = XmL[j]
print(N-cnt)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b

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

for i in range(N):
    x, l = list(map(int, input().split()))
    X.append([x, l])
    X.sort(key=lambda x: x[0], reverse=False)

L = [x[1] for x in X]
X = [x[0] for x in X]

ans = 0
cur = -float('inf')
for i in range(N):
    if (cur <= X[i] - L[i]):
        ans += 1
        cur = X[i] + L[i]
print(ans)

Submission status: Time Limit Exceeded

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

def compare(item):
  return item[1]

newXL = sorted([[x-l, x+l] for x, l in XL], key=compare)

memo = [0]

for i in range(N):
  flag = True
  for j in memo:
    if newXL[i][0] < newXL[j][1]:
      flag = False
  if flag:
    memo.append(i)

print(len(memo))

Submission status: Time Limit Exceeded

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

def compare(item):
  return item[3]

newXL = sorted([[x, l, x-l, x+l] for x, l in XL], key=compare)

memo = [0]

for i in range(N):
  flag = True
  for j in memo:
    if newXL[i][2] < newXL[j][3]:
      flag = False
  if flag:
    memo.append(i)

print(len(memo))

Submission status: Time Limit Exceeded

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

def compare(item):
  return item[3]

newXL = sorted([[x, l, x-l, x+l] for x, l in XL], key=compare)

memo = [0]*N
memo[0] = 1

for i in range(N):
  flag = True
  for j in range(N):
    if memo[j] == 1:
      if newXL[i][2] < newXL[j][3]:
        flag = False
  if flag:
    memo[i] = 1

print(sum(memo))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

blocked = [0] * n
total = 0
for i in range(n):
    ax, al = XL[i]
    for j in range(i + 1, n):
        bx, bl = XL[j]
        if ax - al < bx - bl < ax + al or ax - al < bx + bl < ax + al:
            blocked[i] -= 1
            blocked[j] -= 1
            total += 1
count = 0
heapq.heapify(blocked)
while total > 0:
    total += heapq.heappop(blocked)
    count += 1

print(n - count)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def solve(n, XL):
    blocked = [0] * n
    total = 0
    for i in range(n):
        ax, al = XL[i]
        for j in range(i + 1, n):
            bx, bl = XL[j]
            if ax - al < bx - bl < ax + al or ax - al < bx + bl < ax + al:
                blocked[i] -= 1
                blocked[j] -= 1
                total += 1
    count = 0
    heapq.heapify(blocked)
    while total > 0:
        total += heapq.heappop(blocked)
        count += 1
    return n - count

_n = int(input())
_XL = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _XL))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ar = []
z = 0
for i in range(n):
    a,b = map(int,input().split(" "))
    count = 0
    br = []
    for i in range(a-(b-1),a+b):
        if i in ar:
            count += 1
            break
        br.append(i)
    if count == 0:
        z += 1
        for r in br:
            ar.append(r)
print(z)

Submission status: Time Limit Exceeded

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

num = int(input())
lista=[]
ans = 0
for i in range(num):
  j= list(map(int, input().split()))
  a=j[0]-j[1]
  b=j[0]+j[1]
  lista.append([a,b])
lista.sort(key=lambda x: x[1])

def list_func(x):
  global ans
  xa=[i for i in x if i[0]>=x[0][1]]
  ans+=1
  return xa
for i in range(num):
  lista=list_func(lista)
  if len(lista)==0:
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
lista=[]
ans = 0
for i in range(num):
  j= list(map(int, input().split()))
  a=j[0]-j[1]
  b=j[0]+j[1]
  lista.append([a,b])
lista.sort(key=lambda x: x[1])

def list_func(x):
  global ans
  xa=[i for i in x if i[0]>=x[0][1]]
  ans+=1
  return xa
for i in range(num):
  lista=list_func(lista)
  if len(lista)==0:
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
lista=[]
ans = 0
for i in range(num):
  j= list(map(int, input().split()))
  a=j[0]-j[1]
  b=j[0]+j[1]
  lista.append([a,b])
lista.sort(key=lambda x: x[1])

def list_func(x):
  global ans
  xa=[i for i in x if i[0]>=x[0][1]]
  ans+=1
  return xa
while(len(lista)):
  lista=list_func(lista)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
robot = []
for _ in range(n):
    x, l = map(int, input().split())
    arm_left = x - l
    arm_right = x + l
    robot.append([arm_left, arm_right])

robot.sort(key=lambda x: x[1])
count = 0
while True:
    if len(robot) == 0:
        break
    count += 1
    current_right = robot[0][1]
    robot = [i for i in robot if i[0] >= current_right]

print(count)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n = int(input())
xl= [list(map(int,input().split())) for a in range(n)]

st = []
for x,l in xl:
    s, t = x-l,x+l
    st.append((s,t))

st = sorted(st, key=itemgetter(1))

visited = [1 for a in range(n)]
for j in range(n):
    if visited[j]==1:
        removed = st[j][1]
    for i in range(j+1,n):

        if st[i][0]<removed:
            visited[i]=0
    
print(sum(visited))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
from functools import lru_cache
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    local_robots = copy.deepcopy(robots)
    for i, current in enumerate(robots):
        if count_collisions(current, local_robots) > 0:
            local_robots.remove(current)
            total -= 1
        else:
            break
            
    return total

def count_collisions(current, robots):
    count = 0
    for robot in robots:
        if collision(current[0], current[1], robot[0], robot[1]):
            count += 1
    return count

@lru_cache(maxsize=None)
def collision(currentX, currentL, robotX, rootL):
    return robotX < currentX and robotX+ rootL > currentX - currentL or currentX < robotX and currentX + currentL > robotX - rootL

N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = list(reversed(sorted(ROBOTS, key=lambda x: count_collisions(x, ROBOTS))))
print(solve(ROBOTS))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
from functools import lru_cache
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    local_robots = copy.deepcopy(robots)
    for i, current in enumerate(robots):
        if count_collisions(current, local_robots) > 0:
            local_robots.remove(current)
            total -= 1
        else:
            prev = current
            
    return total

def count_collisions(current, robots):
    count = 0
    for robot in robots:
        if collision(current[0], current[1], robot[0], robot[1]):
            count += 1
    return count

@lru_cache(maxsize=None)
def collision(currentX, currentL, robotX, rootL):
    return robotX < currentX and robotX+ rootL > currentX - currentL or currentX < robotX and currentX + currentL > robotX - rootL

N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = list(reversed(sorted(ROBOTS, key=lambda x: count_collisions(x, ROBOTS))))
print(solve(ROBOTS))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    local_robots = copy.deepcopy(robots)
    for i, current in enumerate(robots):
        if count_collisions(current, local_robots) > 0:
            local_robots.remove(current)
            total -= 1
        else:
            prev = current
            
    return total
    
def count_collisions(current, robots):
    count = 0
    for robot in robots:
        if robot[0] < current[0] and robot[0] + robot[1] > current[0] - current[1]:
            count += 1
        if current[0] < robot[0] and current[0] + current[1] > robot[0] - robot[1]:
            count += 1
    return count

N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = list(reversed(sorted(ROBOTS, key=lambda x: count_collisions(x, ROBOTS))))
print(solve(ROBOTS))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
machines = [list(map(int, input().split())) for i in range(n)]
machines_dic = {}
for item in machines:
    machines_dic[item[0] - item[1]] = item[0] + item[1]

machines_dic = sorted(machines_dic.items(), key=lambda x: x[-1])
count = 0

decided_pairs = []
for pairs in machines_dic:
    flag = False
    pairs_range = [i for i in range(pairs[0] + 1, pairs[1])]
    pairs_range = set(pairs_range)
    for decided_pair in decided_pairs:
        pairs_decided = [i for i in range(decided_pair[0] + 1, decided_pair[1])]
        pairs_decided = set(pairs_decided)
        if len(pairs_decided & pairs_range) != 0:
            flag = True 
            break
    if flag:
        pass
    else:
        decided_pairs.append(pairs)
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
NumOfData = int(input())

arms = {} # {'i':{'x':x, 'l':l, 'N':[n, , , , ,]}}

for I in range(NumOfData):

    inline = input().rstrip().split(' ')
    X, L = [int(j) for j in inline]
    N = []

    for i, e in arms.items():
        x_len = abs(X-e['x'])
        if x_len < L+e['l']:
            N.append(i)
            arms[i]['n'].append(I)

    arms[I] = {'x':X, 'l':L, 'n':N}

sum_overlap = sum([len(e['n']) for e in arms.values()])
sorted_arms = [i for i , e in sorted(arms.items(), key=lambda x: len(x[1]['n']))][-1]

# if sum_overlap <= 0, no overlap
while sum_overlap > 0:
    i = sorted_arms
    e = arms.pop(i)

    # remove label of sorted_arms['n']
    for j in e['n']:
        arms[j]['n'].remove(i)

    # update
    sorted_arms = [i for i , e in sorted(arms.items(), key=lambda x: len(x[1]['n']))][-1]
    sum_overlap = sum([len(e['n']) for e in arms.values()])

print(len(arms))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m_list = []
for i in range(n):
  X, L = map(int, input().split())
  m_list.append([X-L,X+L])
 
m_list = sorted(m_list, key=lambda x:x[1])
  
def MachineArrangementCheck():
  length = len(m_list)
  # 配列の上限エラー対策
  for i in range(length):
    if i != length - 1:      
      # m1の上限とm２の下限が接するかを確認
      if (m_list[i+1][0] - m_list[i][1]) < 0:
        del m_list[i+1]
        return False
  return True
 
while MachineArrangementCheck() == False:
  continue
  
print(len(m_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

X = {}

for _ in range(N):
    x, l_i = map(int, input().split())
    X[x] = (x - l_i, x + l_i)

X_sorted = sorted(X.items(), key=lambda x: x[1][1] - x[1][0], reverse=True)

fts = []

for x in X_sorted:
    ft = (x[1][0] + 1, x[1][1] - 1)
    for f in fts:
        if (ft[0] or ft[1]) in range(f[0], f[1] + 1):
            X_sorted.remove(x)
            del ft
            break
    try:
        fts.append(ft)
    except NameError:
        pass

print(len(X_sorted))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
LeftEnd = [0 for i in range(n)]
Center = [0 for i in range(n)]
RightEnd = [0 for i in range(n)]
for i in range(n):
  robot, arm = map(int, input().split())
  LeftEnd[i] = robot - arm
  Center[i] = robot
  RightEnd[i] = robot + arm

now_rightend = min(RightEnd)

for counter in range(n):
  next_candidates = [RightEnd[i] for i, v in enumerate(LeftEnd) if v >= now_rightend]
  if not next_candidates:
    break
  now_rightend = min(next_candidates)

print(counter+1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

X = {}

for _ in range(N):
    x, l_i = map(int, input().split())
    X[x] = (x - l_i, x + l_i)

X_sorted = sorted(X.items(), key=lambda x: x[1][1] - x[1][0], reverse=True)

fts = []

for x in X_sorted:
    ft = (x[1][0] + 1, x[1][1] - 1)
    for f in fts:
        if (ft[0] or ft[1]) in range(f[0], f[1] + 1):
            X_sorted.remove(x)
            break
    fts.append(ft)

print(len(X_sorted))

Submission status: Time Limit Exceeded

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

x = []*n
y = []*2

for i in range(n):
  y.append(h[i][0]-h[i][1]) #腕が届く地点の最小値
  y.append(h[i][0]+h[i][1]) #腕が届く地点の最大値
  x.append(y) #xに保存
  y = []*2 #yを初期化

x.sort(key = lambda x:x[1]) #腕が届く地点の最大値が小さい順にソート

k = 0 #配列xのtale
con = -10 ** 10

for i in range(n):
  if con > x[k][0]:
    x.pop(k)
  else:
    con = x[k][1]
    k += 1	#taleを一個後ろに下げる

print(len(x)) #要素数(残ったロボットの数)を出力

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
N = int(input())
XL = [list(map(int,input().split())) for _ in range(N)]
area = sorted([[x-l,x+l] for x,l in XL], key=lambda x: x[1])
area_ = [area[0]]
for i in range(1,N):
  if reduce(lambda x,y: x and (area[i][0]>=y[1]), area_, True):
    area_.append(area[i])
print(len(area_))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N=int(input())
XL=[]
def LR(x,l):
   return (x-l,x+l)
def overlap(a,b):
  return a[1]>b[0]

for i in range(N):
    xl=input().split()
    XL += [LR(int(xl[0]),int(xl[1]))]
XL=sorted(XL,key=lambda x:x[0])

def index():
    return list(itertools.combinations(list(range(N)), 2))
def index_in(index,n):
    return [i for i in index if n in i]
def index_out(index,n):
    return [i for i in index if n not in i]

def get_OL(index):
    return { i:overlap(XL[i[0]],XL[i[1]]) for i in index }
OL= get_OL(index())
def n_OL(ix):
  return [sum([1 for i in index_in(ix,n) if OL[i]==True]) for n in range(N)]

def get_max_index(ix):
  ol=n_OL(ix)
  for i in range(len(ix)):
    if ol[i]==max(ol):
      return i
    
def remove_maxOL():
    ix = index()
    n_ol=n_OL(ix)
    count=N
    while sum(n_ol)>0:
        count -= 1
        maxi = get_max_index(ix)
        ix = index_out(ix,maxi)
        n_ol=n_OL(ix)
    return count
  
if __name__=='__main__':
   print(remove_maxOL())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

machines = []
for i in range(n):
  x, l = map(int, input().split())
  machines.append([x+l, x-l])
machines.sort()

stock = []
stock.append(machines.pop(0))
while len(machines) > 0:
  point = machines.pop(0)
  if stock[-1][0] > point[1]:
    continue
  else:
    stock.append(point)

print(len(stock))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = []
    xl = {}
    tmp = []
    tmp2 = []
    maxtmp = 0
    for i in range(n):
        xx, ll = map(int,input().split())
        if maxtmp < xx:
            maxtmp = xx
        low = max(xx-ll+1,0)
        high = xx+ll-1
        lmh = [low,xx,high]
        tmp.append(lmh)
        tmp2.append(lmh)
        x.append(xx)


    tmp.sort()

    # for i in range()
    flg = 0
    for i, a in enumerate(tmp):
        if flg == 0:

            low = a[0]
            high = a[2]
            flg = 1
        else:

            if low <= a[0] and high >= a[0]:
                 aa= tmp2.pop(tmp2.index(a))


        if i+1 < len(tmp) and high < tmp[i+1][0]:
            flg = 0
    print(len(tmp2))
    return


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    x = []
    xl = {}
    maxtmp = 0
    for i in range(n):
        xx, ll = map(int,input().split())
        if maxtmp < xx:
            maxtmp = xx
        xl[xx] = ll
        x.append(xx)
    
    temp = [[] for i in range(maxtmp+2)]
    for i in range(maxtmp+1):
        if i in xl.keys():
            for j in range(i-xl[i]+1, i+xl[i]):
                if j < 0 or j > maxtmp+1:
                    continue
                temp[j].append(i)


    for i,a in enumerate(temp):
        if len(a) <= 1:
            continue
        else:
            for j in range(1,len(a)):
                if a[j] in x:
                    v = x.index(a[j])
                    x.pop(v)
    print(len(x))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
Robo = []
for i in range(n):
  x, leng = map(int, input().split())
  Robo.append([x - leng + 1, x + leng - 1])
Robo.sort(key=lambda x: x[1])
#print(Robo)

Robo_r = []
for robo_cand in Robo:
  l, r = robo_cand
  for robo_r in Robo_r:
    if l <= robo_r[1]:
      break
  else:
    Robo_r.append(robo_cand)
print(len(Robo_r))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
robolist =[[]]*N
for i in range(N):
  robolist[i] = list(map(int, input().split()))
robolist.sort()
robos = []
for k in range(N):
  judge = True
  for l in range(N):
    if (not k == l) and (robolist[k][0] - robolist[k][1] <= robolist[l][0] - robolist[l][1]) and (robolist[l][0] + robolist[l][1] <= robolist[k][0] + robolist[k][1]):
      judge = False
  if judge:
    robos.append(k)

nrobo = 1
xmax = robolist[0][0] + robolist[0][1]
for j in range(1,N):
  if xmax <= robolist[j][0] - robolist[j][1]:
    nrobo += 1
    xmax = robolist[j][0] + robolist[j][1]
print(nrobo)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#N, M = map(int, input().split())
N = int(input())

mt = np.zeros([N, 30])
for i in range(N):
    x, l = map(int, input().split())
    mt[i,max(0,x-l):x+l] = 1

flag = 1    
if np.max(np.sum(mt, axis=0))==1:
    flag = 0
# print(mt)    
cnt = 0
while flag:
    cnt += 1
    tmp = np.sum(mt, axis=0)
    ID = np.argmax(tmp)
    tmp_max = 0
    tmp_id = -1
    for i in reversed(range(N)):
        if mt[i, ID] == 1:
            # print(tmp_id, ID, mt[i],mt)
            a = np.sum(mt[i])
            if  a > tmp_max:
                tmp_max = a
                tmp_id = i

    mt[tmp_id] = 0
    #         np.delete(mt, i, 0)
    # mt[mt[:, ID] == 1] = 0
    # print(np.sum(mt, axis=0), np.max(np.sum(mt, axis=0)))
    if np.max(np.sum(mt, axis=0))==1:
        flag = 0
            
print(N- cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
y = np.array([
    list(map(int, input().split())) for i in range(n)
])
robot = np.array(sorted(y, key=lambda x: x[1], reverse=True))
ans = 0
now = set()

for i in range(n):
    robot_i = robot[-1]
    robot = robot[:-1]
    i_range = set(np.arange(
        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 += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
y = np.array([
    list(map(int, input().split())) for i in range(n)
])
robot = sorted(y, key=lambda x: x[1], reverse=True)
ans = 0
now = set()

for i in range(n):
    robot_i = robot[-1]
    robot = robot[:-1]
    i_range = set(np.arange(
        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 += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
b=[]
for i in a:
	ma=i[0] + i[1]
	mi=i[0] - i[1]
	c=[mi,ma]
	b.append(c)


while True:
	count=[]
	for i in range(n):
		count.append(0)
	p=0
	d=list(itertools.combinations(range(n), 2))
	for i in d:
		p+=1
		if b[i[0]][0]<b[i[1]][0]<b[i[0]][1] or b[i[0]][0]<b[i[1]][1]<b[i[0]][1]:
			count[i[0]]+=1
			count[i[1]]+=1
	del b[count.index(max(count))]
	n-=1
	if sum(count)==0:
		break
print(len(count))

Submission status: Time Limit Exceeded

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

P.sort(key=lambda x: x[0]+x[1])

leave = []
for i in range(N):
    # ロボットpiが既に残すと決めたロボットに重ならないことをチェック
    # print('Checking Robot P{}: {}'.format(i, P[i])) 
    # print('S:{} P:{} T:{}'.format(P[i][0]-P[i][1], P[i][0] , P[i][0]+P[i][1]))
    
    if len(list([leave_ for leave_ in leave if leave_[0] + leave_[1] > P[i][0] - P[i][1]])) == 0:
        leave.append(P[i])
        #print(leave)
    else:
        #print('Not Added')
        #print(leave)
        continue

print(len(leave))

Submission status: Time Limit Exceeded

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

XL = sorted(XL, key=lambda x: x[0]+x[1])

ans = [0]
for i in range(1, N):
    can_put = True
    for j in ans:
        # ぶつかった場合
        if XL[i][0] - XL[i][1] < XL[j][0] + XL[j][1] and XL[j][0] - XL[j][1] < XL[i][0] + XL[i][1]:
            can_put = False
    if can_put:
        ans.append(i)

print(len(ans))

Submission status: Time Limit Exceeded

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

for i in range(0, n):
  str1 = input()
  lst2 = str1.split(' ')
  num1 = int(lst2[0])
  num2 = int(lst2[1])
  lst.append([num1,num2])
                

ranges = []
for i in range(0, n):
  lst3 = []
  lst3.append(lst[i][0] - lst[i][1])
  lst3.append(lst[i][0] + lst[i][1])
  ranges.append(lst3)
count = 0
lst4 = []
bool1 = True
for i in range(0, n):
  #print(ranges[i][0], '  ', ranges[i][1])
  for num in range(ranges[i][0]+1, ranges[i][1]):
    if num not in lst4:
      lst4.append(num)
    else:
      bool1 = False
      break
  if bool1== True:
    count += 1
  bool1 = True

print(count)

Submission status: Time Limit Exceeded

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

X = [XL[i][0] for i in range(N)]
L = [XL[i][1] for i in range(N)]

# ぶつかるものを挙げる
def hit(x_ids, in_x_id):
    ans = []
    for i in x_ids:
        # print(X[in_x_id] - L[in_x_id], X[i] + L[i], X[i] - L[i], X[in_x_id] + L[in_x_id])
        if X[in_x_id] - L[in_x_id] < X[i] + L[i] and X[i] - L[i] < X[in_x_id] + L[in_x_id]:
            # print('haitta')
            ans.append(i)
    return ans


# n番目までの入れ方全パターン
dp = [[] for _ in range(N)]
dp[0].append([0])

for i in range(1, N):
# i-1番目まで見たときの最大個数のパターンに
    for j in dp[i-1]:
# i番目のを追加してもぶつからなければ追加
        hitlist = hit(j, i)
        # print('i, j:', i, j)
        # print(hitlist)
        if len(hitlist) == 0:
            dp[i].append(j+[i])
        else:
# ぶつかるなら、i番目を入れないパターンがある
            dp[i].append(j)
# i番目とぶつかるやつが1個ならそれを消してn番目を入れるパターンもある
            if len(hitlist) == 1:
                dp[i].append(j[: hitlist[0]] + j[hitlist[0] :] + [i])

print(len(dp[-1][0]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
b=[]
for i in a:
	ma=i[0] + i[1]
	mi=i[0] - i[1]
	c=[mi,ma]
	b.append(c)


while True:
	count=[]
	for i in range(n):
		count.append(0)
	p=0
	for i in b:
		p+=1
		for j in b:
			if i==j:
				continue
			if i[0]<j[0]<i[1] or i[0]<j[1]<i[1]:
				count[p-1]+=1
	del b[count.index(max(count))]
	n-=1
	if sum(count)==0:
		break

print(len(count))