Постановка задачи:

Имеется n деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом i-ая деталь обрабатывается на первом станке за a_i времени, а на втором — за b_i времени. Каждый станок в каждый момент времени может работать только с одной деталью.

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

Решение задачи описано на e-maxx.ru

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

Опуская доказательства: в решении предлагается отсортировать пары чисел (a_i, b_i) следующим компаратором:

Мы определили некоторое бинарное отношение на множестве пар чисел. Внимание, вопрос: почему этим отношением можно пользоваться как компаратором?

Сначала о плюсах: Это отношение действительно транзитивно.

Давайте это докажем (если вы хотите минусов, эту часть можно пропустить).

Дано: min(a₁, b₂) < min(a₂, b₁), min(a₂, b₃) < min(a₃, b₂).

Доказать: min(a₁, b₃) < min(a₃, b₁)

Доказательство: от противного. Предположим min(a₁, b₃) ≥ min(a₃, b₁)

Есть два варианта:

1) a₁ ≤ b₂

Из этого следует a₁ < a₂, a₁ < b₁. Из нашего предположения получаем, что

Отсюда min(a₁, b₃) ≤ b₃ < min(a₃, b₁)

2) a₁ > b₂

Из этого следует b₂ < a₂, b₂ < b₁.

Отсюда min(a₁, b₃) ≤ b₃ < min(a₃, b₁)

Получили противоречие.

Ч.т.д.

А вот теперь о минусах. Очевидно, это отношение не обладает свойством антисимметричности. Более того: Давайте на множестве пар чисел введем отношение "быть равными" в том смысле, что ни одна из пар не больше другой. . Это отношение транзитивным не является!

Пример: (2, 3) = (1, 1) = (4, 5), но (2, 3) < (4, 5).

Справедливости ради: Можно показать, что если (a₁, b₁) = (a₂, b₂) = (a₃, b₃) и a₂! = b₂, то (a₁, b₁) = (a₃, b₃)

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

Построим ориентированный граф так: Вершины — элементы последовательности, дуга из i в j соответствует p_i < p_j. Тогда наше определение отсортированной последовательности совпадает с топологической сортировкой этого графа.

Мы показали, что ориентированных циклов в этом графе нет, а значит на нем есть топологическая сортировка, т.е. нашу последовательность можно отсортировать.

Но если мы просто передадим наш компаратор в пузырьковую сортировку, то последовательность не будет отсортирована.

Пример: (4, 5), (1, 1), (2, 3)

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

Таким образом, доказательство на e-maxx не верно.