Задача на python 100 баллов. Вася переехал из своего родного города и очень скучает по старым друзьям. К сожалению, Вася снимает маленькую квартиру и одновременно в гости к нему может приехать только один друг.
Каждый друг сказал Васе два числа A и B - с какого по какой день он может приехать в гости. Каждый друг приезжает и уезжает в полдень. Каждый друг может приехать к Васе только один раз и остаться у него на несколько дней. Вася хотел бы, чтобы суммарное количество дней, когда у него в гостях есть кто-нибудь из друзей, было максимальным. Помогите ему определить даты приезда для каждого из друзей так, чтобы они не пересекались (допустима ситуация, что в один день один из друзей приезжает, а другой - уезжает) и суммарное время, когда у Васи в гостях есть кто-то из друзей, было максимальным.
Формат ввода
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи.
В следующих N строках записано по два целых числа Ai и Bi (оба числа от 1 до 109) - возможное время приезда i-го друга.
Формат вывода
Выведите N пар чисел Li и Ri - номера дней, в которые приедет и уедет i-й друг соответственно (Ai ≤ Li ≤ Ri ≤ Bi). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.
Примеры на фото
Ответы
Ответ: vot na python. я перевел ту с c++. если будут какие-то проблемы при компиляции, думаю решишь их.
-------
import random
def main():
N = random.randint(0, 1000)
IO = []
last_day = 0
for i in range(N):
A = random.randint(1, 109)
B = random.randint(1, 109)
IO.append([])
IO[i].append(A)
IO[i].append(B)
IO[i].append(i)
IO.sort()
for i in range(N):
if last_day >= IO[i][1]:
IO[i][0] = -1
IO[i][1] = -1
else:
if last_day < IO[i][0]:
last_day = IO[i][1]
elif last_day >= IO[i][0]:
IO[i][0] = last_day + 1
last_day = IO[i][1]
for i in range(N):
for j in range(N):
if IO[i][2] == i:
print(f"{IO[j][0]} {IO[j][1]}")
break
return
if __name__ == '__main__':
main()
-------