Входной файл содержит информацию о плане проведения собраний в конференц-зале. Для каждого собрания известно время проведения и длительность собрания. Определите, максимальное количество собраний, которое может быть проведено в конференц-зале в течение одного дня. Если одно из собраний заканчивается в ту же минуту, в которую начинается другое выступление, то их можно поставить вместе. Также необходимо определить максимальный перерыв между последними собраниями при их самом оптимальном размещении. Если способов выбрать последнее собрание несколько, выбрать нужно то, длительность которого больше.
В первой строке входного файла находится натуральное число N (N ≤ 1000), обозначающее количество собраний. Каждая из следующих
Запишите в ответ два числа: максимальное количество собраний, которое можно провести, и максимальный перерыв между последними собраниями при их самом оптимальном размещении.
5
10 140
100 10
120 10
131 19
131 49
Ответ к примеру: 3 1.
Приведём решение на языке Python.
f = open('26_59776.txt')
n = int(f.readline())
a=[]
for s in f:
start,dlit=map(int, s.split())
a.append([start + dlit, start])
a.sort()
count=[]
z=0
for i in range(n):
if z==0:
z=a[i][0]
count.append(a[i])
last=i
elif z<=a[i][1]:
z=a[i][0]
count.append(a[i])
last=i
del count[-1]
z=count[-1][0]
for i in range (last, n):
if z==0:
z=a[i][0]
count.append(a[i])
elif z<=a[i][1]:
count.append(a[i])
print(len(count), count[-1][1] - count[-2][0])
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 53 1.
Ответ: 53 1.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильникова на языке Python.
zajav = sorted([list(map(int,s.split())) for s in open('26_59776.txt').readlines()][1:],key=sum)
rasp = [zajav[0]]
while True:
cand = [x for x in zajav if x[0]>=sum(rasp[-1])]
if len(cand)==0:
break
else:
rasp.append(cand[0])
print(len(rasp),max([x[0]-sum(rasp[-2]) for x in zajav]))