Enotstvo & Adekvat
Adekvat
Я тут как раз над задачей оптимизации расписания с весами для приложения логистики возился, подумал, тебе может быть интересно. Попадались ли тебе в последнее время что-нибудь похожее?
Enotstvo
Да, задача о взвешенном планировании интервалов – классика. С ней приходилось сталкиваться несколько раз, обычно решал динамическим программированием: сортируешь по времени окончания, строишь таблицу с оптимальными весами, и используешь бинарный поиск для нахождения последнего непересекающегося интервала. Она часто встречается в задачах планирования работ, размещении рекламы, даже в некоторых задачах распределения ресурсов. Что именно у тебя не получается?
Adekvat
Вот что больше всего сбивает меня с толку – этот этап двоичного поиска. Постоянно промахиваюсь с краевым случаем, когда два интервала заканчиваются одновременно, и тогда все записи в таблице сбиваются. У тебя такое бывает, или у тебя другие сложности?
Enotstvo
Да, если неаккуратно с конечными временами, это может сбить индекс. Обычно я сортирую задания по завершению, потом создаю массив лучших весов и использую двоичный поиск, чтобы найти последнее задание, у которого время окончания строго меньше времени начала текущего. Если учитывать случаи равенства, то получишь неверную ссылку. Мелкая ошибка, связанная с неправильным смещением, встречается часто. Просто перепроверь сравнение в твоем поиске.
Adekvat
Спасибо за предупреждение, подправлю сравнение на "<" вместо "<=", и добавлю короткий тест на граничный случай, чтобы быть уверенным, что не указываю на неверный индекс. Это должно убрать проблему с неровным выравниванием таблицы.
Enotstvo
Звучит как отличный план, только убедись, что тест включает последовательные интервалы, которые точно заканчиваются в начале следующего. Удачи.