Код не проходит все тесты. Заваливается на 7, он не известен - но ошибки в коде не вижу

Рейтинг: 0Ответов: 1Опубликовано: 05.03.2023

На первом курсе одной Школы, учится 1 ≤ N ≤ 109 студентов. При проведении экзаменов студентов рассаживают в ряд, каждого за своей партой. Парты пронумерованы числами от 0 до N - 1.

Известно, что студент, оставшись без наблюдения, открывает телефон и начинает искать ответы на экзамен в поисковике Яндекса.

Поэтому было решено позвать M преподавателей наблюдать за студентами. Когда за студентом наблюдает хотя бы один преподаватель, он стесняется и не идет искать ответы к экзамену. Преподаватель с номером i видит студентов сидящих за партами от bi до ei включительно.

Необходимо посчитать количество студентов, которые все таки будут искать ответы к экзамену в Яндексе

Формат ввода

  • В первой строке находятся два целых числа 1 ≤ N ≤ 109, 1 ≤ M ≤ 104 — число студентов и число преподавателей соответственно.

  • В следующих M строках содержится по два целых числа 0 ≤ bi ≤ ei ≤ N - 1 — парты, за которыми наблюдает i-й преподаватель.

Формат вывода
Выведите одно число — количество студентов оставшихся без наблюдения.

n,m=map(int, str(input()).split())
mass=[]
first=1
last=2
for i in range(m):
    s=str(input()).split()
    s=list(map(lambda x:int(x),s))
    mass.append((s[0],first))
    mass.append((s[1],last))
mass=sorted(mass,key=lambda x: (x[0], x[1]))
k=0
for i in range(1,len(mass)):
    if mass[i][1]==first and mass[i-1][1]==last:
        k=k+mass[i][0]-mass[i-1][0]-1
k=k+n-1-mass[len(mass)-1][0]+mass[0][0]
print(k)

Моя идея в следующем - создаю массив кортежей. Кортеж состоит из номера парты и индекса first - начало отсчета парт, last - конец. Сортирую массив. Как только встречаю последовательность last first - добавляю к количеству парт. В конце прибавляю количество с 0 парты по первую заданную и с последней заданной по последнюю парту(которая есть)

python
Источник: Stack Overflow на русском

Ответы

▲ 0

Додумался, что положение last first может находится внутри first last и поэтому полностью переработал код.

n,m=map(int,input().split())
mass=[]
for i in range(m):
    x,y=map(int,input().split())
    mass.append((x,1))
    mass.append((y,2))
mass=sorted(mass)
s=0
s=s+mass[0][0]-0
s=s+n-1-mass[len(mass)-1][0]
k=0
for j in range(len(mass)-1):
    if mass[j][1]==1:
        k=k+1
    elif mass[j][1]==2:
        k=k-1
    if k==0:
        if mass[j+1][0]-mass[j][0]>0:
            s=mass[j+1][0]-mass[j][0]-1+s
print(s)

Проходит все тесты)