Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба. Определите какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимальный перерыв между двумя последними мероприятиями.
Входные данные.
В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество заявок на проведение мероприятий.
Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное,
Запишите в ответе два числа: максимальное — количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Ответ:
Приведём решение на языке Python.
f = open('26.txt')
n = int(f.readline())
a=[]
for s in f:
start,end=map(int, s.split())
a.append([end, 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
z = count[-2][0]
maxi = count[-1][1] - count[-2][0]
for i in range(last + 1, n):
if z < a[i][1]:
count[-1] = a[i]
if count[-1][1] - count[-2][0] > maxi:
maxi = count[-1][1] - count[-2][0]
print(len(count), maxi)
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 17 35.
Ответ: 17 35.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Ильи Крылова на языке Python.
data = open('26.txt').readlines()[1:]
times = []
for item in data:
time = [int(i) for i in item.split()]
times.append(time)
times.sort(key=lambda x: x[1])
selectedTimes = [times[0]]
for time in times[1:]:
if selectedTimes[-1][1] <= time[0]:
selectedTimes.append(time)
selectedLastElement = selectedTimes[-1]
endingOfThePreLast = selectedTimes[-2][1]
for time in times:
if time[0] > selectedLastElement[0]:
selectedLastElement = time
biggestGapBetweenTwoLastElements = selectedLastElement[0]-endingOfThePreLast
print(len(selectedTimes), biggestGapBetweenTwoLastElements)
Приведём решение Юрия Лысакова на языке Python.
f = open('26.txt')
f.readline()
a, b = [], []
n, k, max1 = 1, 0, 0
for i in f:
a.append(list(map(int,i.split())))
a.sort(key = lambda x: x[1]) # сортируем по времени завершения
b1, b0 = a[0][1], 0 # правые границы последних двух конференцмй
for i in range(1, len(a)):
if a[i][0] >= b1: # условие того, что конференции не пересекаются
n += 1 # количество коференций
b0 = b1
b1 = a[i][1]
k = i # номер последней конференции
for i in range(k, len(a)):
if a[i][0] >= b0:
max1 = max(max1, a[i][0] - b0) # пытаемся найти подходящую последнюю конференцию
print(n, max1)