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:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from functools import lru_cache


def resolve():
    global N, grid

    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    grid = [[int(x) for x in sys.stdin.readline().split()]
            for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    print(dp((), 0))


def canPut(filled, x, l):
    if filled == ():
        return True
    return all([right <= x - l or x + l <= left for (left, right) in filled])

@lru_cache(maxsize=None)
def dp(filled, i):
    if i == N - 1:
        if canPut(filled, *grid[i]):
            return 1
        else:
            return 0

    n_ex = dp(filled, i + 1)
    n_in = 0
    if canPut(filled, *grid[i]):
        x, l = grid[i]
        lf = list(filled)
        n_in = dp(tuple(lf + [(x - l, x + l)]), i + 1) + 1

    return max([n_ex, n_in])


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
2 4
4 3
9 3
100 5"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
8 20
1 10"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
10 1
2 1
4 1
6 1
8 1"""
        output = """5"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n = int(input())
xs = []
for i in range(n):
    x,l = [int(x) for x in input().split(" ")]
    xs.append([x,l])
# print(xs)
def k(x,l):
    ret = 0
    for xl in xs:
        if xl == [x,l]:
            continue
        if (x < xl[0] and xl[0]-xl[1] < x+l) or (x > xl[0] and xl[0]+xl[1] > x-l):
            ret += 1
    return ret
ks = []
delete = 0
def mkks():
    mx = 0
    pl = -1
    for i in range(n-delete):
        ap = k(xs[i][0], xs[i][1])
        if mx < ap:
            mx = ap
            pl = i
        ks.append(k(xs[i][0], xs[i][1]))
    return [mx,pl]
ret = mkks()
#print(ret)
#print(ks)
while True:
    if ret[0] == 0:
        break
    xs.pop(ret[1])
    delete += 1
    ret = mkks()
print(n-delete)

Submission status: Time Limit Exceeded

Solution code:
X = []
L = []
N = int(input())
for i in range(N):
    a,b = input().split()
    a = int(a)
    b = int(b)
    X.append(a)
    L.append(b)
X_range = []
for i in range(N):
    a = []
    a.append(X[i] - L[i])
    a.append(X[i]+L[i])
    X_range.append(a)
count = 100
while count != 0:
    t_count = [0 for i in range(N)]
    for i in range(N):
        for t in range(N):
            if X_range[i][0]< X_range[t][0] and X_range[t][0] < X_range[i][1]:
                t_count[t] += 1
            if X_range[i][0]< X_range[t][1] and X_range[t][1] < X_range[i][1]:
                t_count[t] += 1
    max_index =  t_count.index(max(t_count))
    count = sum(t_count)
    if not count == 0:
        del X_range[max_index]
    N -= 1


    t_count = [0 for i in range(N)]
    for i in range(N):
        for t in range(N):
            if X_range[i][0]< X_range[t][0] and X_range[t][0] < X_range[i][1]:
                t_count[t] += 1
            if X_range[i][0]< X_range[t][1] and X_range[t][1] < X_range[i][1]:
                t_count[t] += 1
    count = sum(t_count)
print(len(X_range))

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

X = [xl[0] for xl in XL]
L = [xl[1] for xl in XL]

i = 0
count = N
while i < count - 1:
  if X[i] + L[i] > X[i+1] - L[i+1]:
    if X[i] + L[i] < X[i+1] + L[i+1]:
      del X[i+1]
      del L[i+1]
    else:
      del X[i]
      del L[i]
    count -= 1
  else:
    i += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

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

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

    noConf = True

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

    if noConf == True:
        break

    lens = []
    for n in range(remain):
        lens.append(len(conflict[n]))

    index = lens.index(max(lens))
    del X[index]
    del L[index]
    remove += 1

print(N - remove)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
fanwei = []

for i in range(a):
    one = input().split()
    one = [int(i) for i in one]
    two = [one[0] - one[1], one[0] + one[1]]
    fanwei.append(two)

fanwei = sorted(fanwei, key=lambda student: student[0] + 100000000000000000000 * student[1])

maxer = 0
for i in range(len(fanwei)):
    now = -100000000000000000000
    ans = 0
    for i in fanwei[i:]:
        down = i[0]
        if down >= now:
            ans += 1
            now = i[1]
    maxer = max(ans, maxer)

print(maxer)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    def getxl():
        x,l=mis()
        return x-l,x+l
    R = [getxl() for _ in range(N)]
    R.sort(key=lambda xl: xl[0])
    @lru_cache(maxsize=2**20)
    def cou(x):
        if R[-1][0] < x:
            return 0
        at = meg(lambda i: x<=R[i][0], N, -1)
        ret = max(cou(R[i][1])+1 for i in range(at, N))
        return ret
    print(cou(-10000000000))

main()

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))
XL.sort()
#print(XL)

ANS = [(0, -1*10**9-1), (1, XL[0][0]+XL[0][1])]
import bisect
for x, l in XL[1:]:
    new_right = x+l
    new_left = x-l
    
    new_num = 0
    for num, right in reversed(ANS):
        if right > new_left:
            continue
        else:
            new_num = max(new_num, num+1)
            break
    bisect.insort(ANS, (new_num, new_right))
    
#ans_num = 0
#for num, _ in ANS:
#    ans_num = max(ans_num, num)
#print(ans_num)
print(ANS[-1][0])

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

#print X, L

iso = [1 for i in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if X[i] < X[j]:
            if X[j]-L[j] < X[i]+L[i]:
                iso[i] = 0
                break
        if X[j] < X[i]:
            if X[i]-L[i] < X[j]+L[j]:
                iso[i] = 0
                break

n = sum(map(lambda x: 1 - x, iso))
#print n
x = [0 for i in range(n)]
l = [0 for i in range(n)]
p = 0
for i in range(N):
    if iso[i]==0:
        x[p] = X[i]
        l[p] = L[i]
        p += 1

#print x, l
if p == 0:
    print N
    exit()

#print "p=",p


def nooverlap(ex):
    for i in range(p):
        if i in ex:
            continue
        for j in range(p):
            if i == j or j in ex:
                continue
            if x[i] < x[j]:
                if x[j]-l[j] < x[i]+l[i]:
                    return 0
            if x[j] < x[i]:
                if x[i]-l[i] < x[j]+l[j]:
                    return 0
    return 1

for c in range(p-1):
    for comb in itertools.combinations([i for i in range(p)], c+1):
        if nooverlap(comb):
            print N-(len(comb))
            exit()

Submission status: Time Limit Exceeded

Solution code:

n = int(input())

x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])

x.sort()

remove = 0
flag = True

while(1):
    flag = True
    
    for k in range(n-1):
      if (x[k+1][0] - x[k][0]) < x[k][1] + x[k+1][1] and x[k+1][0]>0 and x[k][0]>0:
        remove +=1
        x[k+1][0] = -1
       	flag =False
        break

    if flag == True:
        break
    
print (n -remove)

Submission status: Time Limit Exceeded

Solution code:
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]]
# 左端の小さい順にソートして考える
D.sort()

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

robots = []
for _ in range(N):
    robots.append([int(x) for x in input().split()])

lines = []
count = 0
for robot in robots:
    left = robot[0]-robot[1]
    right = robot[0]+robot[1]
    if (left not in lines and right-1 not in lines):
        count += 1
        for x in range(left, right):
            lines.append(x)

print(count)

Submission status: Time Limit Exceeded

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

over_list = []
while True:
  over_list = []
  for i in range(n):
    il = robots[i][0]-robots[i][1]
    ir = robots[i][0]+robots[i][1]
    over = 0
    for j in range(n):
      jl = robots[j][0]-robots[j][1]
      jr = robots[j][0]+robots[j][1]
      if (il < jl and jl < ir) or (il < jr and jr < ir):
        over += 1
    over_list.append(over)
  max_v = max(over_list)
  if max_v == 0:
    break
  max_i = over_list.index(max_v)
  del robots[max_i]
  n -= 1

print (n)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from functools import lru_cache


def resolve():
    global N, grid

    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    grid = [[int(x) for x in sys.stdin.readline().split()]
            for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    print(dp((), 0))


def canPut(filled, x, l):
    if filled == ():
        return True
    return all([right <= x - l or x + l <= left for (left, right) in filled])


def dp(filled, i):
    if i == N - 1:
        if canPut(filled, *grid[i]):
            return 1
        else:
            return 0

    n_ex = dp(filled, i + 1)
    n_in = 0
    if canPut(filled, *grid[i]):
        x, l = grid[i]
        lf = list(filled)
        n_in = dp(tuple(lf + [(x - l, x + l)]), i + 1) + 1

    return max([n_ex, n_in])


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
2 4
4 3
9 3
100 5"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
8 20
1 10"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
10 1
2 1
4 1
6 1
8 1"""
        output = """5"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
r = []
dead = defaultdict(int)
for i in range(n):
    x, l = map(int, input().split())
    r.append((x - l + 1, x + l - 1))
    for d in range(x - l + 1, x + l):
        dead[d] += 1
while max(dead.values()) > 1:
    maxi, maxd = 0, 0
    for i, ri in enumerate(r):
        dd = sum([dead[d] for d in range(ri[0], ri[1] + 1)])
        if dd > maxd:
            maxi = i
            maxd = dd
    for d in range(r[maxi][0], r[maxi][1] + 1):
        dead[d] -= 1
    n -= 1
print(n)

Submission status: Time Limit Exceeded

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


x_l_max =[]
x_l_min =[]

for i in range(N):
    x_l_max.append(int(x_l[i][0]) + int(x_l[i][1]))
    x_l_min.append(int(x_l[i][0]) - int(x_l[i][1]))
    
# print(x_l_min)
# print(x_l_max)
# print(int(x_l[2][0]) )
    
obstacle_cnt_list =[]
obstacle_cnt = -1

for i in range(N):
    for j in range(len(x_l_min)):
        if x_l_min[j] <= int(x_l[i][0]) and int(x_l[i][0]) <= x_l_max[j]:
            obstacle_cnt = obstacle_cnt +1
    obstacle_cnt_list.append(obstacle_cnt)
    obstacle_cnt = -1

# print(obstacle_cnt_list)

max_value = max(obstacle_cnt_list)
max_index = obstacle_cnt_list.index(max_value)

# print(max_index)

# print( N - max_value)

maxIndex = [i for i, x in enumerate(obstacle_cnt_list) if x == max(obstacle_cnt_list)]

# print(maxIndex)
# print(len(maxIndex))

if max_value ==0:
    print(N)
else:
    print(int(N - len(maxIndex)/2))

Submission status: Time Limit Exceeded

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

l = ll[0]
ans = n

for i in range(n-1):
  li = ll[i+1]
  if l[1] > li[0]:
    ans -= 1
  else:
    l = li

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
XL=[]
for i in range(N):
  T=list(map(int,input().split()))
  XL.append(T)
M=[[] for z in range(N)] #M[i]はiと可動範囲がかぶっているロボットの集合
for i in range(N-1):
  for j in range(i+1,N):
    if XL[j][0]-XL[j][1]<XL[i][0]+XL[i][1] and XL[i][0]-XL[i][1]<XL[j][0]+XL[j][1]:
      M[i].append(j)
      M[j].append(i)
c=0
while M != [[] for z in range(N)]:
  Len=[0 for z in range(N)]
  q=0
  p=0
  for i in range(N):
    Len[i]=len(M[i])
    if Len[i]>q:
      q=Len[i]
      p=i
  M[p]=[]
  for i in range(N):
    if (p in M[i]) == True:
      M[i].remove(p)
  c=c+1
print(N-c)

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

rangeList = []
for element in XLList:
    Xi = element[0]
    Li = element[1]
    rangeList.append(range(Xi-Li, Xi+Li))

tmpList = []
for i in range(N):
    continueFlg = True
    for element in tmpList:
        minElement = min(element)
        maxElement = max(element)
        minRangeList = min(rangeList[i])
        maxRangeList = max(rangeList[i])
        if minElement < minRangeList < maxElement or minElement < maxRangeList < maxElement:
            continueFlg = False
            break
    if continueFlg:
        tmpList.append(rangeList[i])
print(len(tmpList))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = [0]*N
L = [0]*N
max = 0
del_count = 0
for i in range(N):
  X[i], L[i]= map(int,list(input().split()))
new_list = sorted(X)
for i in range(N):
  x = X.index(new_list[i])
  if i == 0:
    max = new_list[i] + L[x]
  elif max > new_list[i] - L[x]:
    del_count +=1
  else:
    max = new_list[i] + L[i]
print(N-del_count)

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))
XL.sort()
#print(XL)

ANS = [(-1*10**9-1, 0), (XL[0][0]+XL[0][1], 1)]
for i in range(1, N):
    x = XL[i][0]
    l = XL[i][1]
    new_right = x+l
    new_left = x-l
    
    new_num = 0
    for right, num in ANS:
        if right > new_left:
            continue
        else:
            new_num = max(new_num, num+1)
    ANS.append((new_right, new_num))
    
ans_num = 0
for _, num in ANS:
    ans_num = max(ans_num, num)
print(ans_num)

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)

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


A = []
B = []
for _ in range(N):
  x, l = map(int, input().split())
  A.append(x - l)
  B.append(x + l - 1)

l = []
ans = 0
for i in range(N):
  count = 0
  for j in range(N):
    if i == j:
      continue
    else:
      if A[i] <= A[j] <= B[i] or A[i] <= B[j] <= B[i]:
        count += 1
  l.append(count)
print(N - l.count(max(l)) if max(l) != 0 else N)

Submission status: Time Limit Exceeded

Solution code:
def find_dex(list,dex):
    for j in range(len(list)):
        if list[j][0] == dex:
            return j
    return 0
n = int(input())
d = []
left = []
right = []
for i in range(n):
    x,l = map(int, input().split())
    # num , left , right
    left.append([i,x-l+1,x+l-1])
    right.append([i,x-l+1,x+l-1])

left.sort(key=lambda x:x[1],reverse=False)
right.sort(key=lambda x:x[2],reverse=False)

flag = True
p = 10**9 + 1
ans = 0
while len(left) > 0:
    if flag:
        i,l,r = left.pop(-1)
        right.pop(find_dex(right,i))
        flag = False
        if r >= p:
            ans += 1
        p = l

    else:
        i,l,r = right.pop(-1)
        left.pop(find_dex(left,i))
        flag = True
        if r >= p:
            ans += 1
        p = l

    #print(i,l,r)
    #print(left)
    #print(right)

print(n-ans)

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	ans = 0
	tmp = []
	for i in range(N):
		X,L = inputMap()
		LL = X-L
		RR = X+L
		tmp.append((LL,RR))

	tmp.sort()

	kota = []
	for i,val in enumerate(tmp):
		ki_L,ki_R = val
		for j in range(i+1,len(tmp)):
			hi_L, hi_R = tmp[j]

			if ki_R > hi_L:
				ans += 1

		kota.append(ans)
		ans = 0

	aa = max(kota)
	#print(kota)
	print(N-aa)


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

l = ll[0]
ans = n

for i in range(n-1):
  if l[1] > ll[i+1][0]:
    ans -= 1
  else:
    l = ll[i+1]

print(ans)

Submission status: Time Limit Exceeded

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

d = {}
max_ = 0
for xl in X_L:
  for i in range(xl[0] - xl[1], xl[0] + xl[1]):
    if i not in d:
      d[i] = 1
    else:
      d[i] += 1
    max_ =max(d[i], max_)
print(N - max_ + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
l = []
for i in range(N):
  l.append(list(map(int, input().split())))
ans_l = [0]*N
ans = 0
  
l.sort(key=lambda x : x[1])  

for i in range(N):
  if 1 not in ans_l[l[i][0] - l[i][1] + 1:l[i][0] + l[i][1]]:
    for j in range(l[i][0] - l[i][1] + 1, l[i][0] + l[i][1]):
      try:
        ans_l[j] = 1
      except:
        pass
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X, L, d = [0] * N, [0] * N, [[0, 0]] * N
flag_d = [True] * N
Con = []  # 共通部分を持つペア
Con_count = [0] * N
ans = N

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

# 左端の小さい順にソートして考える
d.sort()

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

while (len(Con) != 0):
    ind = Con_count.index(max(Con_count))
    ans -= 1
    Con = [i for i in Con if not ind in i]
    Con_count[ind] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
input = raw_input
n = int(input())

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

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

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

def find_max_jama():
    max_jama = max(jamas_count)
    if max_jama == 0:
        return None

    max_i = jamas_count.index(max_jama)
    return max_i

n_remove = 0
while True:
    max_i = find_max_jama()
    if max_i is None:
        break

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

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

out = n - n_remove
print(out)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
X = []
for _ in range(N):
  x, l = map(int,input().split())
  X.append([x+l, x, l])
sorted_X = sorted(X, key=lambda x:(x[1], x[2]))
ans = 1
for i in range(N-1):
  temp = 1
  cnt = sorted_X[i][0]
  for j in range(i+1,N):
    if sorted_X[j][1] - sorted_X[j][2] >= cnt:
      temp += 1
      cnt = sorted_X[j][0]
  if temp > ans:
    ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = []
    L = []
    for i in range(N):
        x, l = [int(s) for s in input().split()]
        X.append(x)
        L.append(l)

    ranges = []
    for i in range(N):
        ranges.append((X[i] - L[i], X[i] + L[i]))
    ranges.sort(key=lambda x: x[0])

    while True:
        dup = [0 for i in range(len(ranges))]
        for i in range(len(ranges) - 1):
            if ranges[i][1] > ranges[i + 1][0]:
                dup[i] += 1
                dup[i + 1] += 1

        remove_index = [(i, dup[i]) for i in range(len(dup)) if dup[i] > 0]
        if len(remove_index) == 0:
            break
        remove_index.sort(key=lambda x: x[1], reverse=True)
        ranges.pop(remove_index[0][0])
    print(len(ranges))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
fanwei = []

for i in range(a):
    one = input().split()
    one = [int(i) for i in one]
    two = [one[0] - one[1], one[0] + one[1]]
    fanwei.append(two)

fanwei = sorted(fanwei, key=lambda student: 100000000000000000000 * (1 + student[0]) + student[1])


maxer = 0
for i in range(len(fanwei)):
    now = -100000000000000000000
    ans = 0
    for i in fanwei[i:]:
        down = i[0]
        if down >= now:
            ans += 1
            now = i[1]
    maxer = max(ans, maxer)

print(maxer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
rob = defaultdict(list)
for i in range(n):
    x,l  = map(int,input().split())
    rob[x] = [l,x-l,x+l]
rob = sorted(rob.items(), key=lambda x:x[1])
tmp = []
for idx in range(0,len(rob)-1):
    i,[l,left,right] = rob[idx]
    for idx2 in range(idx+1,len(rob)):
        j,[_,_,_] = rob[idx2]
        if left < j < right:
            tmp.append(idx2)

print(len(rob)-len(set(tmp)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
interval = set([])

times = 0

for i in range(N):
    [X, L] = [int(i) for i in input().split()]
    newinterval = set(range(X-(L-1), X+(L-1)+1))
    if interval.isdisjoint(newinterval):
        times += 1
    interval = interval | newinterval

print(times)