418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 7 - ประวัติรุ่นแก้ไข

Aoy: /* การพิสูจน์ความถูกต้องของอัลกอริทึม */

2009-09-21T13:09:40Z

การพิสูจน์ความถูกต้องของอัลกอริทึม

Aoy: /* การพิสูจน์ความถูกต้องของอัลกอริทึม */

2009-09-21T13:02:36Z

การพิสูจน์ความถูกต้องของอัลกอริทึม

Aoy: /* การพิสูจน์ความถูกต้องของอัลกอริทึม */

2009-09-21T13:02:17Z

การพิสูจน์ความถูกต้องของอัลกอริทึม

Aoy: /* การพิสูจน์ความถูกต้องของอัลกอริทึม */

2009-09-21T12:48:26Z

การพิสูจน์ความถูกต้องของอัลกอริทึม

Aoy: /* การพิสูจน์ความถูกต้องของอัลกอริทึม */

2009-09-19T08:23:42Z

การพิสูจน์ความถูกต้องของอัลกอริทึม

Aoy เมื่อ 08:21, 19 กันยายน 2552

2009-09-19T08:21:34Z

Aoy: /* อัลกอริทึม */

2009-09-19T08:12:50Z

อัลกอริทึม

Aoy: /* อัลกอริทึม */

2009-09-19T08:12:39Z

อัลกอริทึม

Aoy: หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== เรียงเวลาการเข้างานของคนงานตามเวล…'

2009-09-19T08:07:08Z

หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== เรียงเวลาการเข้างานของคนงานตามเวล…'

หน้าใหม่

==''อัลกอริทึม''==
เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก เมื่อพิจารณาเวลาการทำงานของคนงานที่มีเวลาเลิกงานน้อยที่สุด แล้วเลือกคนที่มีเวลาทำงาน 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>

@@ แถว 21: / แถว 21: @@
 ==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==
-จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีขนาดน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สังเกตว่า เนื่องจาก <math> OPT \, </math> เป็นคำตอบที่ดีที่สุด ดังนั้น <math> k \leq m \,</math> เสมอ
+จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีจำนวนน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สังเกตว่า เนื่องจาก <math> OPT \, </math> เป็นคำตอบที่ดีที่สุด ดังนั้น <math> m \leq k \,</math> เสมอ
 สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
-'''lemma:'''สำหรับ <math> r \leq k \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
+'''lemma:'''สำหรับ <math> r \leq m \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
 '''พิสูจน์:'''ทำการพิสูจน์โดย induction บน r กรณี base case <math> r=1 \, </math> เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต <math> S \, </math> เป็นผู้ตรวจงาน ดังนั้น <math> f(i_1) \geq f(j_1) \, </math> จริง
-พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math> ต้องการพิสูจน์ว่า สำหรับค่า <math> f(i_r) \geq f(j_r) \, </math> ด้วย
+พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math> ต้องการพิสูจน์ว่า  <math> f(i_r) \geq f(j_r) \, </math> ด้วย
-พิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> f(i_r) < f(j_r) \,</math> พิจารณาการที่ greedy algorithm เลือกผู้ตรวจงานถึงคนที่ <math> i_{r-1} \, </math> แสดงว่าต้องมีคนงานคนหนึ่งให้เป็นคนที่ <math> k \, </math> ที่มีเวลาเริ่มงานทีหลังผู้ตรวจงานคนที่ <math> i_{r-1} \, </math> นี้ นั่นคือ <math> s_k > f(i_{r-1}) \,</math> เราจะได้ว่าเวลาการทำงานของคนงานคนที่ <math> k \,</math> นี้จะต้อง overlap กับผู้ตรวจงานคนที่ <math> j_r \, </math> ของ <math> OPT \, </math> ด้วย เพราะไม่เช่นนั้นคนที่ <math> k \, </math> นี้ก็จะไม่มีผู้ตรวจงานคนไหน ตรวจงานเค้าได้ (ไม่เป็นไปตามเงื่อนไขของบริษัท) แต่เนื่องจาก greedy algorithm เลือกผู้ตรวจงานเป็นคนงานคนที่มีเวลาเลิกงานช้าที่สุด และในที่นี้ greedy algorithm เลือกคนที่ <math> i_r \,</math> จึงเกิดข้อขัดแย้งที่ว่า <math> f(i_r) < f(j_r) \,</math> ดังนั้นเราสามารถสรุปได้ว่า <math> f(i_r) \geq f(j_r) \,</math> สำหรับ <math> r \leq k \,</math> ใด ๆ
+พิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> f(i_r) < f(j_r) \,</math> พิจารณาการที่ greedy algorithm เลือกผู้ตรวจงานถึงคนที่ <math> i_{r-1} \, </math> แสดงว่าต้องมีคนงานคนหนึ่งให้เป็นคนที่ <math> k \, </math> ที่มีเวลาเริ่มงานทีหลังผู้ตรวจงานคนที่ <math> i_{r-1} \, </math> นี้ นั่นคือ <math> s_k > f(i_{r-1}) \,</math> เราจะได้ว่าเวลาการทำงานของคนงานคนที่ <math> k \,</math> นี้จะต้อง overlap กับผู้ตรวจงานคนที่ <math> j_r \, </math> ของ <math> OPT \, </math> ด้วย เพราะไม่เช่นนั้นคนที่ <math> k \, </math> นี้ก็จะไม่มีผู้ตรวจงานคนไหน ตรวจงานเค้าได้ (ไม่เป็นไปตามเงื่อนไขของบริษัท) แต่เนื่องจาก greedy algorithm เลือกผู้ตรวจงานเป็นคนงานคนที่มีเวลาเลิกงานช้าที่สุด และในที่นี้ greedy algorithm เลือกคนที่ <math> i_r \,</math> จึงเกิดข้อขัดแย้งที่ว่า <math> f(i_r) < f(j_r) \,</math> ดังนั้นเราสามารถสรุปได้ว่า <math> f(i_r) \geq f(j_r) \,</math> สำหรับ <math> r \leq m \,</math> ใด ๆ
 '''ทฤษฎีบท:''' Greedy algorithm ใช้จำนวนผู้ตรวจงานน้อยที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ <math>  k = m \,</math>
@@ แถว 37: / แถว 37: @@
 '''พิสูจน์:''' สมมติเพื่อให้เกิดข้อขัดแย้งว่า <math> m < k \,</math>
-พิจารณาเมื่อ <math> OPT \, </math> เพิ่มคนงานคนที่ <math> j_m \, </math> เข้าไปเป็นผู้ตรวจงาน เนื่องจากผู้ตรวจงาน <math> j_1,j_2,...,j_m \, </math> ตรวจงานคนงานได้ครบทุกคนตามเงื่อนไขของบริษัทแล้ว แสดงว่าไม่มีคนงานคนไหนที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงาน <math> m \, </math> ในวิธีการของ <math> OPT \,</math> และจาก lemma เราได้ว่า <math> f(i_r) \geq f(j_r) \,</math> จึงได้ว่าไม่มีคนงานคนไหนที่ที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงานคนที่ <math> i_m \,</math> ด้วย แต่การที่ greedy algorithm ยังเพิ่มผู้ตรวจงานคนที่ <math> i_{m+1} \,</math> เข้าไปอีก แสดงว่า greedy algorithm ยังทำงานไม่จบ ทั้ง ๆ ที่ควรจบได้แล้ว เพราะคนงานทุกคนมีผู้ตรวจงานที่มีเวลา overlap กับตนเองแล้ว จึงเกิดข้อขัดแย้ง
+พิจารณาเมื่อ <math> OPT \, </math> เพิ่มคนงานคนที่ <math> j_m \, </math> เข้าไปเป็นผู้ตรวจงาน เนื่องจากผู้ตรวจงาน <math> j_1,j_2,...,j_m \, </math> ตรวจงานคนงานได้ครบทุกคนตามเงื่อนไขของบริษัทแล้ว แสดงว่าไม่มีคนงานคนไหนที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงาน <math> m \, </math> คนในวิธีการของ <math> OPT \,</math> และจาก lemma เราได้ว่า <math> f(i_r) \geq f(j_r) \,</math> จึงได้ว่าไม่มีคนงานคนไหนที่ที่มีเวลาทำงานไม่ overlap กับผู้ตรวจงานคนที่ <math> i_m \,</math> ด้วย แต่การที่ greedy algorithm ยังเพิ่มผู้ตรวจงานคนที่ <math> i_{m+1} \,</math> เข้าไปอีก แสดงว่า greedy algorithm ยังทำงานไม่จบ ทั้ง ๆ ที่ควรจบได้แล้ว เพราะคนงานทุกคนมีผู้ตรวจงานที่มีเวลา overlap กับตนเองแล้ว จึงเกิดข้อขัดแย้ง
 ดังนั้น <math> k = m \,</math> และ greedy algorithm ใช้จำนวนผู้ตรวจงานน้อยที่สุดเท่าที่จะเป็นไปได้

@@ แถว 23: / แถว 23: @@
 จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีขนาดน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สังเกตว่า เนื่องจาก <math> OPT \, </math> เป็นคำตอบที่ดีที่สุด ดังนั้น <math> k \leq m \,</math> เสมอ
- สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
+สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
 '''lemma:'''สำหรับ <math> r \leq k \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ

@@ แถว 21: / แถว 21: @@
 ==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==
-จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีขนาดน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
+จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีขนาดน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สังเกตว่า เนื่องจาก <math> OPT \, </math> เป็นคำตอบที่ดีที่สุด ดังนั้น <math> k \leq m \,</math> เสมอ
 '''lemma:'''สำหรับ <math> r \leq k \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
@@ แถว 30: / แถว 32: @@
 พิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> f(i_r) < f(j_r) \,</math> พิจารณาการที่ greedy algorithm เลือกผู้ตรวจงานถึงคนที่ <math> i_{r-1} \, </math> แสดงว่าต้องมีคนงานคนหนึ่งให้เป็นคนที่ <math> k \, </math> ที่มีเวลาเริ่มงานทีหลังผู้ตรวจงานคนที่ <math> i_{r-1} \, </math> นี้ นั่นคือ <math> s_k > f(i_{r-1}) \,</math> เราจะได้ว่าเวลาการทำงานของคนงานคนที่ <math> k \,</math> นี้จะต้อง overlap กับผู้ตรวจงานคนที่ <math> j_r \, </math> ของ <math> OPT \, </math> ด้วย เพราะไม่เช่นนั้นคนที่ <math> k \, </math> นี้ก็จะไม่มีผู้ตรวจงานคนไหน ตรวจงานเค้าได้ (ไม่เป็นไปตามเงื่อนไขของบริษัท) แต่เนื่องจาก greedy algorithm เลือกผู้ตรวจงานเป็นคนงานคนที่มีเวลาเลิกงานช้าที่สุด และในที่นี้ greedy algorithm เลือกคนที่ <math> i_r \,</math> จึงเกิดข้อขัดแย้งที่ว่า <math> f(i_r) < f(j_r) \,</math> ดังนั้นเราสามารถสรุปได้ว่า <math> f(i_r) \geq f(j_r) \,</math> สำหรับ <math> r \leq k \,</math> ใด ๆ

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:48, 21 กันยายน 2552
แถว 27:		แถว 27:
	'''พิสูจน์:'''ทำการพิสูจน์โดย induction บน r กรณี base case <math> r=1 \, </math> เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต <math> S \, </math> เป็นผู้ตรวจงาน ดังนั้น <math> f(i_1) \geq f(j_1) \, </math> จริง		'''พิสูจน์:'''ทำการพิสูจน์โดย induction บน r กรณี base case <math> r=1 \, </math> เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต <math> S \, </math> เป็นผู้ตรวจงาน ดังนั้น <math> f(i_1) \geq f(j_1) \, </math> จริง

−	พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math>	+	พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math> ต้องการพิสูจน์ว่า สำหรับค่า <math> f(i_r) \geq f(j_r) \, </math> ด้วย
		+
		+	พิสูจน์โดยข้อขัดแย้ง สมมติให้ <math> f(i_r) < f(j_r) \,</math> พิจารณาการที่ greedy algorithm เลือกผู้ตรวจงานถึงคนที่ <math> i_{r-1} \, </math> แสดงว่าต้องมีคนงานคนหนึ่งให้เป็นคนที่ <math> k \, </math> ที่มีเวลาเริ่มงานทีหลังผู้ตรวจงานคนที่ <math> i_{r-1} \, </math> นี้ นั่นคือ <math> s_k > f(i_{r-1}) \,</math> เราจะได้ว่าเวลาการทำงานของคนงานคนที่ <math> k \,</math> นี้จะต้อง overlap กับผู้ตรวจงานคนที่ <math> j_r \, </math> ของ <math> OPT \, </math> ด้วย เพราะไม่เช่นนั้นคนที่ <math> k \, </math> นี้ก็จะไม่มีผู้ตรวจงานคนไหน ตรวจงานเค้าได้ (ไม่เป็นไปตามเงื่อนไขของบริษัท) แต่เนื่องจาก greedy algorithm เลือกผู้ตรวจงานเป็นคนงานคนที่มีเวลาเลิกงานช้าที่สุด และในที่นี้ greedy algorithm เลือกคนที่ <math> i_r \,</math> จึงเกิดข้อขัดแย้งที่ว่า <math> f(i_r) < f(j_r) \,</math> ดังนั้นเราสามารถสรุปได้ว่า <math> f(i_r) \geq f(j_r) \,</math> สำหรับ <math> r \leq k \,</math> ใด ๆ

@@ แถว 23: / แถว 23: @@
 จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีขนาดน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
-''lemma:''สำหรับ <math> r \leq k \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
+'''lemma:'''สำหรับ <math> r \leq k \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
-''พิสูจน์''ทำการพิสูจน์โดย induction บน r กรณี base case <math> r=1 \, </math> เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต <math> S \, </math> เป็นผู้ตรวจงาน ดังนั้น <math> f(i_1) \geq f(j_1) \, </math> จริง
+'''พิสูจน์:'''ทำการพิสูจน์โดย induction บน r กรณี base case <math> r=1 \, </math> เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต <math> S \, </math> เป็นผู้ตรวจงาน ดังนั้น <math> f(i_1) \geq f(j_1) \, </math> จริง
 พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:21, 19 กันยายน 2552
แถว 19:		แถว 19:
	}		}
	</geshi>		</geshi>
		+
		+	==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==
		+	จะใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> G=\{i_1,i_2,...,i_k \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก greedy algorithm ข้างต้น และ <math> OPT=\{j_1,j_2,...,j_m \} \, </math> เป็นเซตของผู้ตรวจงานที่ได้จาก optimal algorithm (อัลกอริทึมสำหรับการแก้ปัญหาข้างต้นที่ให้เซตของผู้ตรวจงานที่มีขนาดน้อยที่สุด) เราจะทำการพิสูจน์โดยบอกว่า <math> k = m \,</math> สมมติให้เวลาการเข้างานของ <math> OPT \, </math> ถูกเรียงตามเวลาเลิกงานจากน้อยไปมากด้วย
		+
		+	''lemma:''สำหรับ <math> r \leq k \,</math> ใด ๆ แล้ว <math> f(i_r) \geq f(j_r) \,</math> เสมอ
		+
		+	''พิสูจน์''ทำการพิสูจน์โดย induction บน r กรณี base case <math> r=1 \, </math> เนื่องจาก greedy algorithm เลือกคนงานที่มีเวลาเลิกงานช้าที่สุดที่ overlap กับคนงานที่มีเวลาเลิกงานน้อยที่สุดที่กำลังพิจารณาในเซต <math> S \, </math> เป็นผู้ตรวจงาน ดังนั้น <math> f(i_1) \geq f(j_1) \, </math> จริง
		+
		+	พิจารณากรณีที่ <math> r > 1 \, </math> สมมติให้ข้อความที่ต้องการพิสูจน์เป็นจริงสำหรับค่า <math> r-1 \, </math> นั่นคือ <math> f(i_{r-1}) \geq f(j_{r-1}) \, </math>

@@ แถว 13: / แถว 13: @@
       l = {m in S| min f(m)} // ให้ l เป็นคนงานที่มีเวลาทำงาน overlap กับ คนงานคนที่ i ที่เลิกงานช้าที่สุด
            G = G union l // เพิ่มคนงาน l เข้าไปในเซตของผู้ตรวจงาน
-     Ol = {k in S| s(k) <= f(l) or s(l) <= f(k)} // Ol เป็นเซตของคนงานทุกคนในเซตของคนงานที่กำลังพิจารณาที่มีเวลาทำงาน overlap กับผู้ตรวจงาน l
+          Ol = {k in S| s(k) <= f(l) or s(l) <= f(k)} // Ol เป็นเซตของคนงานทุกคนในเซตของคนงานที่กำลังพิจารณาที่มีเวลาทำงาน overlap กับผู้ตรวจงาน l
       S= S - Ol
+     }

@@ แถว 1: / แถว 1: @@
 ==''อัลกอริทึม''==
-เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก เมื่อพิจารณาเวลาการทำงานของคนงานที่มีเวลาเลิกงานน้อยที่สุด แล้วเลือกคนที่มีเวลาทำงาน overlap กับคนงานนี้ที่มีเวลาเลิกงานช้าที่สุดเป็นผู้ตรวจงาน จากนั้นลบคนงานทุก ๆ คนที่มีเวลาทำงาน overlap กับผู้ตรวจงานคนนี้ออกจากเซตของคนงานที่กำลังพิจารณา ทำแบบนี้ไปเรื่อย ๆ จนเซตของคนงานที่กำลังพิจารณาเป็นเซตว่าง
+เรียงเวลาการเข้างานของคนงานตามเวลาเลิกจากน้อยไปหามาก เมื่อพิจารณาเวลาการทำงานของคนงานที่มีเวลาเลิกงานช้าที่สุด แล้วเลือกคนที่มีเวลาทำงาน overlap กับคนงานนี้ที่มีเวลาเลิกงานช้าที่สุดเป็นผู้ตรวจงาน จากนั้นลบคนงานทุก ๆ คนที่มีเวลาทำงาน overlap กับผู้ตรวจงานคนนี้ออกจากเซตของคนงานที่กำลังพิจารณา ทำแบบนี้ไปเรื่อย ๆ จนเซตของคนงานที่กำลังพิจารณาเป็นเซตว่าง
 <geshi lang="c">
@@ แถว 6: / แถว 6: @@
+{
      G = empty set // ให้ G เป็นเซตของผู้ตรวจงาน
-    S = {1,2,...,n} // เซตของคนงานที่กำลังพิจารณา ที่เรียงตามเวลาเลิกงานจากน้อยไปมาก นั่นคือ f1 <= f2 <= ... <= fn นั่นเอง
+        S = {1,2,...,n} // เซตของคนงานที่กำลังพิจารณา ที่เรียงตามเวลาเลิกงานจากน้อยไปมาก นั่นคือ f1 <= f2 <= ... <= fn นั่นเอง
          while S not empty do
+     {
-      i = {j in S| min_j f(j)}
+      i = {j in S| min f(j)} // i เป็นคนงานในเซตของคนงานที่กำลังพิจารณาที่มีเวลาเลิกงานช้าที่สุดตอนนี้
+     }
+}
 </geshi>