Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и минимальное возможное суммарное время проведения всех мероприятий.
Входные данные.
В первой строке входного файла находится натуральное число N — количество заявок на проведение мероприятий (натуральное число, не превыщающее 1000).
Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятия (каждое из чисел натуральное, не превосходящее 1440).
Запишите в ответе два числа через пробел: максимальное количество мероприятий и минимальное суммарное время проведения всех мероприятий.
Решение при помощи программы:
f=open(’6_26_conf__3uzor.txt’) #Открываем файл
n=int(f.readline())
requests=[list(map(int,i.split())) for i in f] # считываем и записываем в список все конференции
requests.sort(key = lambda x:(x[1],x[1]-x[0])) # сортируем список конференций для того чтобы мы могли взять наибольшее количество конференций для проведения и при этом сумма их длительностей была как можно меньше
hall=[] # список конференций, которые мы проведём
for start,end in requests: # проход по всем конференциям
if not hall or start>=hall[-1][1] :
hall.append([start,end,end-start]) # добавляем конференцию в список, если её начало позже или равно окончанию предыдущей конференции
times=sorted([x for x in requests], key = lambda x:(x[1]-x[0],x[0])) # создаём новый список, в нём будут записаны время проведения конференции по возрастанию их длительности
c=0
for i in times:
for j in range(0,len(hall)-1):
# если конференция i длится меньше времени чем конференция из списка hall, и при этом конференцию i можно поставить в расписание при этом не нарушив условие
if (i[1]-i[0]) < (hall[j][2]) and (hall[j+1][0] >= i[1]) and (i[0] > hall[j][0]):
hall[j]=[i[0],i[1],i[1]-i[0]] # тогда заменяем конференцию
break # приостанавлием цикл для того чтобы перейти к следующей конференции i
print(len(hall))
c=sum([i[2] for i in hall])
print(c)