Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. в каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба.
Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные.
В первой строке входного файла находится
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Пример входного файла:
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам
Ответ:
Приведём решение на языке Python.
f = open('0.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
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])
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 32 15.
Ответ: 32 15.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Ильи Крылова на языке Python.
data = open('26_2024.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)
selectedLastTime = selectedTimes[-1]
for time in times:
if selectedLastTime[1] <= time[0]:
selectedLastTime = time
print(len(selectedTimes), selectedLastTime[0]-selectedTimes[-2][1])
Приведём решение Евгения Соколова на языке Python.
f = open('26_2024.txt')
f.readline()
a = [list(map(int, s.split())) for s in f]
f.close()
b = []
while len(a) > 0:
a.sort(key = lambda e: e[1])
b.append(a[0])
fin = a[0][1]
a = list(filter(lambda e: e[0] >= fin, a))
print(len(b))
print(b[len(b)-1][0] - b[len(b)-2][1])
Приведём решение Юрия Красильникова на языке Python.
a = sorted([list(map(int,s.split())) for s in open('26_2024.txt')][1:],key=lambda x: x[1])
b = [a[0]]
while True:
c = [x for x in a if x[0]>=b[-1][1]]
if len(c)==0: break
else: b.append(c[0])
print(len(b),max(x[0]-b[-2][1] for x in a))