Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия.
Входные данные.
В первой строке входного файла находится натуральное
Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное,
Запишите в ответе два числа: максимальное — количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия (в минутах от начала суток).
Типовой пример организации данных во входном файле:
5
10 150
100 110
131 170
131 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, по заявкам
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Ответ:
Приведём решение на языке 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
del count[-1]
z=count[-1][0]
for i in range (last+1,n):
if z==0:
z=a[i][0]
count.append(a[i])
elif z<=a[i][1]:
count.append(a[i])
print(len(count), max(count, key = lambda d: d[0])[0])
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 16 1345.
Ответ: 16 1345.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Ильи Крылова на языке Python.
s = open('26.txt').readlines()[1:]
times = []
for item in s:
time = [int(i) for i in item.split()][::-1]
times.append(time)
times = sorted(times)
times = [i[::-1] for i in times]
selectedTimes = [times[1]]
times = times[1:]
for time in times:
if selectedTimes[-1][1] <= time[0]:
selectedTimes.append(time)
biggestStartTime = selectedTimes[-2][1]
biggestEndingTime = max([i[1] for i in times if biggestStartTime <= i[0]])
print(len(selectedTimes), biggestEndingTime)