Дано: В офисе имеется комната для переговоров, сотрудники подают заявки для проведения совещаний в переговорке. Каждая заявка содержит время начала и время окончания совещания. Задача, спланировать расписание таким образом, что бы удовлетворить максимальное число заявок.
Схематично это можно представить так (верхняя линия — время работы переговорки, нижние линии — заявки на проведение совещания):
Алгоритм решения сводится к тому, что бы выбрать заявки с минимальным временем окончания. Т.е. сортируем все заявки по времени окончания, на первом шаге выбираем совещание которое закончится раньше всех (т.е. первый элемент в отсортированном по времени окончания списке), далее по очереди просматриваем остальные заявки и удовлетворяем т.е. в которых время начала переговоров больше или равно времени освобождения переговорки.
# Множество содержащие заявки на переговоры , для простоты (время начала, время окончания) переговоров # представленно целыми числами 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)]