โปรแกรมหาจำนวนคอร์สสูงสุดที่เรียนได้จากช่วงเวลาใน Python

สมมติว่าเรามีรายการช่วงเวลาในรูป [start, end] แสดงเวลาเริ่มต้นและสิ้นสุดของคอร์ส เราต้องหาจำนวนคอร์สสูงสุดที่เรียนได้ โดยเรียนทีละคอร์ส และคอร์สถัดไปต้องเริ่มหลังจากคอร์สก่อนหน้าจบสิ้นสุด

ตัวอย่าง

อินพุต: times = [[3, 6], [6, 9], [7, 8], [9, 11]]

เอาต์พุต: 3

คอร์สที่เลือก: [3, 6], [7, 8], [9, 11]

ขั้นตอนการแก้ปัญหา

ใช้วิธี Greedy (ขี้เกียจ) โดยจัดเรียงตามเวลาสิ้นสุด:

1. เรียงลำดับ times ตามค่า end จากน้อยไปมาก
2. กำหนด counter = 0, end = -1
3. วนลูปผ่านแต่ละช่วงเวลา:
   • ถ้า times[i][0] > end ให้เพิ่ม counter และตั้ง end = times[i][1]
4. คืนค่า counter

การนำไปใช้ใน Python

class Solution:
    def solve(self, times):
        times.sort(key=lambda x: x[1])
        counter = 0
        end = -1
        for i in range(len(times)):
            if times[i][0] > end:
                counter += 1
                end = times[i][1]
        return counter

ob = Solution()
times = [
    [3, 6],
    [6, 9],
    [7, 8],
    [9, 11]
]
print(ob.solve(times))

อินพุต

[[3, 6], [6, 9], [7, 8], [9, 11]]

เอาต์พุต

3