Ежедневный бит (е) C ++ # 128, Общая задача на собеседовании: максимальная прибыль для графика работы.
Имея список из N заданий, каждое из которых имеет время начала, время окончания и прибыль, определите максимальную прибыль, достижимую при обработке некоторых заданий при условии, что ни одно из них не перекрывается.
Предположим, что время начала и окончания находится в диапазоне {0..50000} и полуоткрытый интервал для времени начала и окончания, т. е. задание может начаться во время окончания предыдущего задания.
Например, в приведенном выше списке профессий наиболее прибыльный график состоит из двух зеленых профессий с общей прибылью 55.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/TqedjPoEo.
Решение
Если мы переборщим это решение, то получим сложность O(2^n), и может показаться, что это правильный подход, поскольку планирование заданий — это NP-задача. Однако, поскольку у нас есть данные о времени начала и окончания заданий, это намного проще.
Учтите следующее: если мы рассматриваем задание Q, то максимально возможная прибыль будет либо без выполнения задания, т. е. максимальная прибыль, достижимая в start_time+1, либо выполнение задания, т. е. прибыль от задания + максимальная прибыль, достижимая в end_time .
Это уже указывает на простое решение динамического программирования, обрабатывающее задания в порядке убывания времени их запуска.
Однако мы выберем другое решение.
Если мы просматриваем задания в порядке их начала, мы можем связать задание Q с предыдущей последовательностью заданий, время окончания которых совпадает со временем начала этого задания или раньше, и мы хотим выбрать лучший (наиболее прибыльный). ) такая последовательность.
Здесь нам нужны два наблюдения:
- независимо от того, какие последовательности мы цепляем, мы получаем одно и то же время окончания, только разную прибыль, поэтому для каждого задания мы генерируем только одну цепочку.
- последовательности, которые были допустимой цепочкой для текущего задания, также будут допустимой цепочкой для всех будущих заданий (поскольку их время начала совпадает с текущим заданием или позже него), поэтому нам не нужно запоминать их (только их прибыль и только лучший)
Собрав это вместе, мы получим решение O(n*log(n)):
struct Job {
int start_time;
int end_time;
int profit;
};
struct Chain {
int end_time;
int profit;
bool operator<(const Chain& other) const {
return end_time > other.end_time;
}
};
int most_profit(std::vector<Job> jobs) {
// Sort the jobs by start_time, ascending
std::ranges::sort(jobs, {}, &Job::start_time);
int profit = 0;
// Existing chains, sorted by end_time (min-heap)
std::priority_queue<Chain> chains;
// For every job in start time order
for (auto &job : jobs) {
// Process all existing chains that can chain with this job
while (!chains.empty() &&
job.start_time >= chains.top().end_time) {
profit = std::max(profit, chains.top().profit);
chains.pop();
}
// Create a new chain, whose profit is the profit of
// this job + best profit upto start_time
chains.push(Chain{job.end_time, job.profit + profit});
}
// Process the remaining chains
while (!chains.empty()) {
profit = std::max(profit, chains.top().profit);
chains.pop();
}
return profit;
}
