Условие

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

Для каждого поезда известно:

• номер поезда,
• время прибытия,
• время, которое у вас займёт разгрузка,
• сумма, которую вам заплатят за разгрузку этого поезда.

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

Необязательно браться за разгрузку всех поездов. На станции есть другие грузчики.

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

Очень желательны тесты. Было бы прекрасно также получить несколько слов о реализованном

Brute Force

Пусть дано n поездов.

Переберем битовую маску от 0 до 2^n - 1.
Для каждой маски:

• Возьмем поезда, которым соответствует единичный бит в маске
• Проверим, что временные рамки выбранных поездов не пересекаются
• Посчитаем заработок

Перебрав все маски находим лучший план на день (с максимальным заработком).

Этот алгоритм был реализован для тестирования второго решения.

Advanced Solution

Поскольку сами длины отрезков для решения не важны, можно решить проблему больших значений времени методом сжатия координат. Тогда у всех поездов время начала/конца разгрузки будет в интервале [0, 2n).

Теперь решим задачу с помощью динамического программирования:
Поезд у нас разгружается во временной интервал [start, start + duration). Задачу мы решаем в целых временах (например, unixtime).

Можно считать, что поезд разгружается во временной отрезок [start, start + duration - 1], поскольку в момент времени start + duration уже можно приступать к разгрузке следующего поезда.

Пусть d[i] - максимальный заработок за первые i единиц времени.

Выполнено следующее реккурентное соотношение:
d[i] = max(d[i - 1], d[t.start - 1] + t.reward), где t - поезд с t.start + t.duration - 1 == i.

То есть либо ничего не делаем последнюю секунду, либо в эту секунду мы заканчиваем обработку какого-то поезда. В первом случае вознаграждение с предыдущей секунды не изменяется. Во втором к сумме, которую платят за разгрузку этого поезда, добавляется ответ для времени перед началом разгрузки этого поезда.

Тогда ответом будет d[2n - 1].

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

Сложность:

O(n * log(n)), поскольку O(n * log(n)) сжатие координат и O(n) динамика.