Bit(e) harian C++ #128, Masalah wawancara umum: Keuntungan maksimum untuk jadwal pekerjaan.

Diberikan daftar N pekerjaan, masing-masing dengan waktu mulai, waktu berakhir dan keuntungan, tentukan keuntungan maksimum yang dapat dicapai dengan memproses beberapa pekerjaan di bawah batasan bahwa tidak ada yang tumpang tindih.

Asumsikan waktu mulai dan waktu berakhir dalam rentang {0..50000} dan interval setengah terbuka untuk waktu mulai dan berakhir, yaitu suatu pekerjaan dapat dimulai pada waktu berakhirnya pekerjaan sebelumnya.

Misalnya, dalam daftar pekerjaan di atas, jadwal yang paling menguntungkan terdiri dari dua pekerjaan ramah lingkungan, dengan total keuntungan sebesar 55.

Sebelum Anda melanjutkan membaca solusinya, saya mendorong Anda untuk mencoba menyelesaikannya sendiri. Berikut ini tautan Compiler Explorer dengan beberapa kasus uji: https://compiler-explorer.com/z/TqedjPoEo.

Larutan

Jika kita memaksakan solusi ini secara kasar, kita akan mendapatkan kompleksitas O(2^n), dan sepertinya ini adalah pendekatan yang tepat karena penjadwalan pekerjaan adalah masalah NP. Namun, karena kita mempunyai waktu mulai dan berakhirnya pekerjaan yang diberikan kepada kita, masalah ini menjadi jauh lebih mudah.

Pertimbangkan hal berikut: jika kita mempertimbangkan pekerjaan Q, keuntungan maksimum yang mungkin adalah tidak menjalankan pekerjaan, yaitu keuntungan maksimum yang dapat dicapai pada waktu_mulai+1, atau menjalankan pekerjaan, yaitu keuntungan pekerjaan + keuntungan maksimum yang dapat dicapai pada waktu_akhir .

Ini sudah menunjuk pada solusi pemrograman dinamis sederhana, memproses pekerjaan dalam urutan waktu mulainya.

Namun, kami akan mencari solusi berbeda.

Jika kita memindai pekerjaan berdasarkan urutan waktu mulainya, kita dapat merangkai pekerjaan Q ke urutan pekerjaan sebelumnya yang waktu berakhirnya pada atau sebelum waktu mulai pekerjaan ini, dan kita ingin memilih yang terbaik (paling menguntungkan). ) urutan seperti itu.

Kami memerlukan dua pengamatan di sini:

  • tidak peduli urutan mana yang kita rantai, kita akan mendapatkan waktu akhir yang sama, hanya keuntungan yang berbeda, jadi untuk setiap pekerjaan, kita hanya menghasilkan satu rantai
  • urutan yang merupakan rantai yang valid untuk pekerjaan saat ini juga akan menjadi rantai yang valid untuk semua pekerjaan di masa depan (karena waktu mulainya adalah pada atau setelah pekerjaan saat ini), jadi kita tidak perlu mengingatnya (hanya keuntungannya, dan hanya yang terbaik)

Jika digabungkan, kita akan mendapatkan solusi 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;
}

"Buka solusinya di Compiler Explorer."