Дано: В офисе имеется комната для переговоров, сотрудники подают заявки для проведения совещаний в переговорке. Каждая заявка содержит время начала и время окончания совещания. Задача, спланировать расписание таким образом, что бы удовлетворить максимальное число заявок.
Схематично это можно представить так (верхняя линия — время работы переговорки, нижние линии — заявки на проведение совещания):
Алгоритм решения сводится к тому, что бы выбрать заявки с минимальным временем окончания. Т.е. сортируем все заявки по времени окончания, на первом шаге выбираем совещание которое закончится раньше всех (т.е. первый элемент в отсортированном по времени окончания списке), далее по очереди просматриваем остальные заявки и удовлетворяем т.е. в которых время начала переговоров больше или равно времени освобождения переговорки.
# Множество содержащие заявки на переговоры , для простоты (время начала, время окончания) переговоров
# представленно целыми числами
s = {(1, 2), (3, 6), (3, 4), (5, 7), (1, 7)}
def actsel(mitings_times):
approved_time = []
mitings_times = sorted(mitings_times, key=lambda x: x[1])
approved_time.append(mitings_times.pop(0))
for miting in mitings_times:
if miting[0] >= approved_time[-1][1]:
approved_time.append(miting)
return approved_time
print(actsel(s))
# >>> [(1, 2), (3, 4), (5, 7)]