418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 7
รุ่นแก้ไขเมื่อ 08:07, 19 กันยายน 2552 โดย Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== เรียงเวลาการเข้างานของคนงานตามเวล…')
อัลกอริทึม
เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก เมื่อพิจารณาเวลาการทำงานของคนงานที่มีเวลาเลิกงานน้อยที่สุด แล้วเลือกคนที่มีเวลาทำงาน overlap กับคนงานนี้ที่มีเวลาเลิกงานช้าที่สุดเป็นผู้ตรวจงาน จากนั้นลบคนงานทุก ๆ คนที่มีเวลาทำงาน overlap กับผู้ตรวจงานคนนี้ออกจากเซตของคนงานที่กำลังพิจารณา ทำแบบนี้ไปเรื่อย ๆ จนเซตของคนงานที่กำลังพิจารณาเป็นเซตว่าง
<geshi lang="c"> Supervisor() {
G = empty set // ให้ G เป็นเซตของผู้ตรวจงาน
S = {1,2,...,n} // เซตของคนงานที่กำลังพิจารณา ที่เรียงตามเวลาเลิกงานจากน้อยไปมาก นั่นคือ f1 <= f2 <= ... <= fn นั่นเอง
while S not empty do
{
i = {j in S| min_j f(j)}
}
} </geshi>
