упорядочивает процессы в возрастающем времени выполнения, оптимальный способ создания набора неперекрывающихся процессов?

Question

находятся п рабочих мест в наборе, каждый со времен начала S _я и финишные раз F _я для п _я

Я пытаюсь выяснить, если рабочие места заказа в заказе по возрастанию время начала, время окончания и интервал времени (f _i - s _i) является оптимальным или нет.

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

Далее я сказал, что заказ в возрастающем времени окончания был оптимальным, потому что справа, когда добавляется время окончания, следующее быстродействующее завершающее задание добавляется, увеличивая количество заданий, добавленных в список неперекрывающихся заданий.

Однако я не уверен, о упорядочении ф _я - s _я является оптимальным.

Моя логика такова, что он является оптимальным, поскольку он будет список самых коротких рабочих мест, которые я считаю, что добавить или рассмотреть рабочие места, которые охватывают длины других работ последних

EDIT: Оптимизация за счет максимального размера Неправительственный -overlapping процессы список

Answer 1

Я думаю, что есть удивительно простая стратегия для выбора следующего задания, которое дает вам подмножество с максимальным количеством последовательных рабочих мест: среди рабочих мест слева, которые имеют действительное время начала (в начале : все начальные значения действительны, после того как первое задание было выбрано, время начала следующего задания должно, конечно, не предшествовать когда заданное ранее задание) всегда выбирает работу с самым ранним временем окончания.

Доказательство того, что эта стратегия является оптимальной, может начинаться следующим образом: предположим, что у вас есть оптимальное (то есть максимальное) подмножество последовательных заданий и что первое задание не является заданием с (общим) самым ранним временем окончания, тогда это задание с общим ранним временем окончания не может быть в оптимальном подмножестве, но вы можете заменить первое задание оптимального подмножества этой работой, и вы получите еще одно оптимальное подмножество, которое имеет работу с самым ранним временем окончания в качестве первой работы. Теперь вы можете продолжить то же самое со вторым заданием, и, следовательно, ясно, что в подмножестве, сгенерированном с помощью вышеупомянутой стратегии, n-е задание имеет время окончания, которое не превышает время окончания n-го задания любого оптимальное подмножество для любого n, и, следовательно, созданное таким образом подмножество также является оптимальным.