ТеоремаАлгоритм GREEDY-ACTIVITY-SELECTION дает набор из наибольшего возможного количества совместных заявок.
Доказательство.
Заявки отсортированы по возрастанию времени окончания.
Прежде всего докажем, что существует оптимальное решение задачи о выборе заявок, содержащее заявку номер 1 (с самым ранним временем окончания).
В самом деле, если в каком-то оптимальном множестве заявок заявка номер 1 не содержится, то можно заменить в нём заявку с самым ранним временем окончания на заявку номер 1, что не повредит совместности заявок (ибо заявка номер 1 кончается ещё раньше, чем прежняя, и ни с чем пересечься не может) и не изменит их общего количества.
Стало быть, можно искать оптимальное множество заявок А среди содержащих заявку номер 1: существует оптимальное решение, начинающееся с жадного выбора. После того как мы договорились рассматривать только наборы, содержащие заявку номер 1, все несовместные с ней заявки можно выкинуть, и задача сводится к выбору оптимального набора заявок из множества оставшихся заявок (совместных с заявкой номер 1).
Другими словами, мы свели задачу к аналогичной задаче с меньшим числом заявок. Рассуждая по индукции, получаем, что, делая на каждом шаге жадный выбор, мы придём к оптимальному решению