Стабильность транзакций

Для начала заметим интересный факт, для двух транзакций ai < aj, нет смысла разбивать транзакцию ai, но не разбивать транзакцию aj, так как максимум в такой ситуации точно не измениться, а минимум может уменьшится, то есть ухудшить ответ.

Второй полезный факт: разбивать всегда надо на две равные части по тем же самым соображениям.

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

Переберем все k, найдем оптимальный ответ. Сложность решения .