Входной файл содержит информацию о плане проведения собраний в конференц-зале. Для каждого собрания известно время начала и окончания собрания.
Определите максимальное количество собраний, и время между началом первого мероприятия и окончанием последнего. Если способов выбрать последнее собрание несколько, выбрать нужно то, длительность которого больше.
В первой строке входного файла находится натуральное число N (N ≤ 1000), обозначающее количество собраний. Каждая из следующих
Запишите в ответ два числа: максимальное количество собраний и время между началом первого мероприятия и окончанием последнего.
Типовой пример организации данных во входном файле:
5
10 150
100 110
120 130
131 150
131 180
Ответ:
Приведём решение Михаила Кузнецова на языке Python.
f = open('26.txt')
n = int(f.readline())
a = []
for s in f:
a.append(list(map(int,s.split())))
a.sort(key=lambda x: x[1])
t = a[0][1] #время окончания последнего мероприятия
meet = [a[0]]
for i in range(1, n):
if t <= a[i][0]:
t = a[i][1]
meet.append(a[i])
last_i = i
tp = meet[-1][1] #время окончания последнего мероприятия
T = meet[-1][1] - meet[-1][0] #длительность последнего мероприятия
del meet[-1]
t = meet[-1][1] #время окончания предпоследнего мероприятия
for i in range(last_i + 1, n):
if t <= a[i][0]:
if T < a[i][1] - a[i][0]:
T = a[i][1] - a[i][0]
tp = a[i][1]
print(len(meet)+1, tp - meet[0][0])
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 16 1008.
Ответ: 16 1008.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильникова на языке Python.
zajav = sorted([list(map(int,s.split())) for s in open('26.txt')][1:],key=lambda x: x[1])
rasp = [zajav[0]]
while True:
kand = [z for z in zajav if z[0]>=rasp[-1][1]]
if len(kand) == 0:
break
else:
rasp.append(kand[0])
kand = sorted([z for z in zajav if z[0] >= rasp[-2][1]],key=lambda x: x[1]-x[0])
rasp[-1] = kand[-1]
print(len(rasp),rasp[-1][1]-rasp[0][0])