ข้อนี้ให้ตารางขนาด $N \times N$ และต้องการให้เก็บมูลค่ารวมได้มากที่สุดจากตารางนี้โดยทุกการเก็บจะใช้เวลา 1 นาทีและช่องที่ $(i,j)$ จะไหม้และเก็บไม่ได้หาก $i+j < 2+t$ เมื่อ $t$ คือเวลาในนาที (เช่นช่อง $(2,2)$ จะเก็บได้เมื่อ $t\leq2$ กล่าวคือต้องเก็บในนาทีแรกหรือนาทีที่ 2 หากจะเก็บ) ไฟจะไหม้ครบทุกช่องหลังเวลาที่ $2N-2$

โจทย์ข้อนี้เป็นโจทย์ Greedy กล่าวคือในแต่ละขั้นควรเลือกของที่ดีที่สุด

Greedy Algorithm

เราสามารถพิสูจน์ว่าหากวางแผนการเลือกย้อนจากนาทีสุดท้ายมาถีงนาทีแรก ในแต่ละนาทีหากเลือกของที่มีมูลค่ามากสุดที่ยังไม่ได้วางแผนว่าจะเลือกจะทำให้ได้ผลรวมมากสุด

สังเกตว่าหากนับนาทีย้อนลงมาในแต่ละนาทีที่ลดลงจะมีตัวเลือกมากขึ้นเรื่อยๆ (เพราะมีของที่ยังไม่ไหม้มากขึ้น) และไม่มีตัวเลือกไหนหายไปหากไม่ได้เลือก เช่นในนาทีสุดท้าย $t=2N -2$ จะเหลือเพียงของที่ $(N,N)$ ที่เก็บได้และควรเก็บอันนั้น และในนาทีก่อนหน้านั้น $t=2N -3$ ต้องเลือกจาก $(N-1,N)$ และ $(N,N-1)$ และในนาที $t=2N -4$ จะต้องเลือกจาก $(N-2,N), (N-1, N-1), (N, N-2)$ และอันที่ยังไม่ได้เลือกจาก $(N-1,N)$ กับ $(N,N-1)$

เราจะพิสูจน์ว่าในเวลาที่ $t$ สามารถเลือกของที่มูลค่ามากสุดจากอันที่ยังไม่ไหม้และยังไม่ได้วางแผนว่าจะเลือกในเวลาอื่นที่ช้ากว่า $t$ เพื่อให้ได้ผลรวมสูงสุด ให้ของดังกล่าวเป็นชิ้น $X_t$ และให้การเลือกของ Algorithm ที่อธิบายไว้เป็น $X_1, X_2, \dots, X_{2N-2}$

สมมติว่าการเลือกที่ได้ผลรวมมากที่สุดคือ $O_1, O_2, \dots, O_{2N-2}$ นั่นคือในเวลา $t$ จะเลือกของชิ้นที่ $O_t$ พิจารณา $t$ สุดท้ายที่ $O_t \neq X_t$ มีอยู่สองกรณีคือชิ้น $X_t$ ถูกเลือกในเวลา $t_2 < t$ ซึ่งแปลว่ามี $O_{t_2} = X_t$ หรือ $X_t$ ไม่ถูกเลือกเลย ในกรณีแรกเราสามารถสลับการเลือก $O_{t_2}$ กับ $O_t$ (เพราะทั้งสองจะยังไม่ไหม้ในเวลา $t_2 < t$) เพื่อให้ได้ลำดับใหม่ที่มี $O_t=X_t$ ส่วนในกรณีที่สองสามารถสลับ $O_t$ มาเป็นการเลือก $X_t$ ในเวลา $t$ แทนเพราะมูลค่าของ $X_t$ มีค่าไม่น้อยกว่าค่าอื่นใดๆ ที่ยังไม่ถูกเลือก (เนื่องจาก $O_{t+1}, O_{t+2}, \dots, O_{2N-2}$ ตรงกับ $X_{t+1}, X_{t+2}, \dots, X_{2N-2}$ ตามที่สมมติไว้)

ดังนั้นแปลว่ามีการเลือกที่ได้ผลรวมมากสุด $O_1, O_2, \dots, O_{2N-2}$ โดยที่ $O_t = X_t$ สำหรับทุก $t$ กล่าวคือการเลือก $X_1, X_2, \dots, X_{2N-2}$ เป็นการเลือกที่ได้ผลรวมมากที่สุดแบบหนึ่ง

Solution

เราสามารถ Implement การเลือกค่ามากสุดที่ยังไม่ถูกเลือกด้วย Priority Queue นั่นคือจาก $t=2N-2$ ถึง $1$ เราจะ Push ค่าของของชิ้นที่อยู่ที่ $(i,j)$ ทุกตัวที่ $i+j = t + 2$ เข้าไปใน Priority Queue และ Pop ค่ามากสุดใน Queue ออกมาเป็นตัวที่ถูกเลือกในเวลา $t$

Priority Queue จะมีการ Push $\mathcal{O}(N^2)$ รอบ (หนึ่งครั้งสำหรับทุกค่าในตาราง) และการ Pop $\mathcal{O}(N)$ รอบ (หนึ่งครั้งสำหรับทุก $t$) การ Push และ Pop ต่างใช้เวลา $\mathcal{O}(\log N^2) = \mathcal{O}(\log N)$ ดังนั้นเวลาทั้งหมดคือ $\mathcal{O}(N^2 \log N)$ ซึ่งเร็วเพียงพอสำหรับ $N=1000$