Пример счетчика для алгоритма планирования работы «Самое раннее время окончания»

Question

Ну, у нас есть жадный алгоритм планирования заданий (планирование максимального количества заданий). мы можем использовать различные методы

1. Кратчайшей работу первого
2. Самого раннее время начала первого
3. Работа с минимальными конфликтами первых
4. Самого раннее время окончания первого

У меня есть встречный пример первых три но я не смог найти встречный пример для четвертого.

вот примеры счетчика для первых трех методов

кратчайшей Работа Первый:

Здесь мы можем запланировать 2 рабочие места вместо одного короче.

Самое раннее время начала первой:

Здесь мы можем запланировать 6 меньшую работу, которая начинается позже, а не на тот, который начнется раньше

Работа с минимальными конфликтами первый:

Здесь мы можем запланировать 4 задания с конфликтами 3,4,4,3 вместо 3 с минимальными конфликтами, то есть 2,3,3

Итак, что бы счетчик пример последнего одного Самое раннее время окончания первого я не мог найти пример счетчика для этого. Таким образом, он всегда дает оптимальное решение для каждого набора данных?

UPDATE 1:

У меня есть один исполнитель, чтобы выполнить задание, и я хочу, чтобы выполнить максимальное количество рабочих мест.

Answer 1

Самое раннее время начала Первое - это жадный алгоритм, который дает оптимальный алгоритм для вышеупомянутой проблемы. (На самом деле проблема, о которой вы упомянули, называется проблемой Interval Scheduling)

Доказательство может быть выполнено с использованием charging argument. Вы сравниваете результат жадного алгоритма с оптимальным решением и утверждаете, что решение не хуже оптимального.