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