การเลือกกิจกรรมตามเวลาสิ้นสุดที่เร็วที่สุด

เมื่อมีกิจกรรมพร้อมเวลาเริ่มต้นและสิ้นสุด การเลือกกิจกรรม จะถามว่าคุณสามารถเข้าร่วมกิจกรรมได้มากที่สุดกี่กิจกรรมโดยไม่มีสองกิจกรรมใดทับซ้อนกัน 📅

กิจกรรมสองกิจกรรม ขัดแย้งกัน หากกิจกรรมหนึ่งเริ่มก่อนที่อีกกิจกรรมจะสิ้นสุด คุณเลือกได้เพียงหนึ่งกิจกรรมจากคู่ที่ทับซ้อนกัน

กุญแจของวิธีแบบละโมบคือเลือกกิจกรรมที่ สิ้นสุดเร็วที่สุด จากกิจกรรมที่ยังเลือกได้เสมอ การสิ้นสุดเร็วจะเหลือพื้นที่เวลาให้กิจกรรมอื่นมากที่สุด

เริ่มด้วยการ เรียงลำดับ กิจกรรมทั้งหมดตามเวลาสิ้นสุด จากนั้นตัวเลือกถัดไปที่ดีที่สุดก็คือกิจกรรมถัดไปในลำดับที่ยังใส่ได้

เก็บตัวแปรหนึ่งตัวสำหรับเวลาสิ้นสุดของกิจกรรมล่าสุดที่เลือก กิจกรรมใหม่ต้องเริ่มต้นที่เวลานี้หรือหลังจากนั้นจึงจะเข้ากันได้

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

ต้นทุนอยู่ที่ sort ซึ่งใช้ O(n log n) แล้วจึงไล่ผ่านเชิงเส้นเพียงครั้งเดียว วิธีนี้เร็วพอแม้อินพุตการแข่งขันจะมีขนาดใหญ่มาก

การสิ้นสุดก่อนจะทำให้เส้นเวลาว่าง เร็วที่สุด จึงไม่มีทางขัดขวางแผนที่ดีกว่า การสลับกิจกรรมนี้เข้าไปในตารางที่ดีที่สุดใด ๆ ก็ยังให้ผลดีเท่าเดิม

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

ตัดสินใจว่ากิจกรรมที่สิ้นสุดตรงกับเวลาที่อีกกิจกรรม เริ่มต้น นับเป็นความขัดแย้งหรือไม่ ใช้ s >= เวลาสิ้นสุดล่าสุดเพื่ออนุญาตให้กิจกรรมต่อกันพอดี

รูปแบบนี้ซ่อนอยู่เบื้องหลังโจทย์มากมาย เช่น การจอง ห้อง การดูรายการ หรือการจัดงานให้ทำงาน มองให้ออกแล้วใช้กฎสิ้นสุดเร็วที่สุดได้

ต้องการจำนวนกิจกรรมที่ไม่ทับซ้อนกันให้ได้มากที่สุด

เรียงลำดับกิจกรรมตาม เวลาสิ้นสุด แล้วเลือกแต่ละกิจกรรมที่เริ่มหลังจากกิจกรรมล่าสุดที่เลือกสิ้นสุด การเรียงลำดับหนึ่งครั้งกับการไล่ผ่านหนึ่งครั้งให้เซตที่มีขนาดใหญ่ที่สุด 🚀