โปรแกรมหาจำนวนกล่องที่สร้างโซ่ยาวที่สุดใน Python

สมมติว่าเรามีรายการกล่อง แต่ละกล่องมีค่า [start, end] (โดย start < end) เราสามารถต่อกล่องสองกล่องได้หาก end ของกล่องหนึ่งเท่ากับ start ของอีกกล่อง เป้าหมายคือหาความยาวของโซ่กล่องที่ยาวที่สุด

ตัวอย่าง

อินพุต: boxes = [[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]

เอาต์พุต: 4

โซ่ที่ยาวที่สุด: [1, 2] -> [2, 4] -> [4, 5] -> [5, 6]

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

ใช้ Dynamic Programming กับ dictionary:

1. ถ้า boxes ว่าง คืนค่า 0
2. เรียงลำดับ boxes
3. สร้าง dic เป็น defaultdict(int) เก็บความยาวโซ่สูงสุดที่ลงท้ายด้วยค่า end
4. วนลูปผ่านแต่ละคู่ (s, e) ใน boxes:
   • dic[e] = max(dic[e], dic[s] + 1)
5. คืนค่า max(dic.values())

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

import collections

class Solution:
    def solve(self, boxes):
        if not boxes:
            return 0
        boxes.sort()
        dic = collections.defaultdict(int)
        for s, e in boxes:
            dic[e] = max(dic[e], dic[s] + 1)
        return max(dic.values())

ob = Solution()
boxes = [
    [4, 5],
    [5, 6],
    [4, 8],
    [1, 2],
    [2, 4]
]
print(ob.solve(boxes))

อินพุต

[[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]

เอาต์พุต

4