บิตรายวัน (e) ของ C++ #128 ปัญหาการสัมภาษณ์ทั่วไป: กำไรสูงสุดสำหรับตารางงาน
เมื่อพิจารณารายการงาน N งาน โดยแต่ละงานมีเวลาเริ่มต้น เวลาสิ้นสุด และกำไร ให้กำหนดผลกำไรสูงสุดที่สามารถทำได้โดยการประมวลผลงานบางงานภายใต้ข้อจำกัดที่ไม่มีทับซ้อนกัน
สมมติว่าเวลาเริ่มต้นและสิ้นสุดภายในช่วง {0..50000} และช่วงเวลาครึ่งเปิดสำหรับเวลาเริ่มต้นและสิ้นสุด กล่าวคือ งานสามารถเริ่มต้นในเวลาสิ้นสุดของงานก่อนหน้าได้
ตัวอย่างเช่น ในรายการงานด้านบน ตารางงานที่ทำกำไรได้มากที่สุดประกอบด้วยงานสีเขียวสองงาน โดยมีกำไรรวม 55
ก่อนที่คุณจะอ่านวิธีแก้ปัญหาต่อ ฉันขอแนะนำให้คุณลองแก้ไขด้วยตนเอง นี่คือลิงก์ Compiler Explorer พร้อมกรณีทดสอบสองสามกรณี: https://compiler-explorer.com/z/TqedjPoEo
สารละลาย
หากเราบังคับใช้วิธีแก้ปัญหานี้อย่างดุเดือด เราจะจบลงด้วยความซับซ้อน O(2^n) และอาจดูเหมือนว่านี่จะเป็นแนวทางที่ถูกต้องเนื่องจากการกำหนดเวลางานเป็นปัญหา NP อย่างไรก็ตาม เนื่องจากเรามีเวลาเริ่มต้นและสิ้นสุดของงานที่มอบหมาย ปัญหานี้จึงง่ายกว่ามาก
พิจารณาสิ่งต่อไปนี้: หากเรากำลังพิจารณางาน Q กำไรสูงสุดที่เป็นไปได้อาจเป็นการไม่ได้รันงาน เช่น กำไรสูงสุดที่ทำได้ที่ start_time+1 หรือการรันงาน เช่น กำไรของงาน + กำไรสูงสุดที่ทำได้ ณ เวลาสิ้นสุด .
สิ่งนี้ชี้ไปที่โซลูชันการเขียนโปรแกรมแบบไดนามิกอย่างง่าย โดยประมวลผลงานตามลำดับเวลาเริ่มต้นจากมากไปหาน้อย
อย่างไรก็ตาม เราจะไปหาวิธีแก้ปัญหาอื่น
หากเราสแกนงานตามลำดับเวลาเริ่มต้น เราสามารถเชื่อมโยงงาน 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;
}
