Chương trình tìm chuỗi hộp dài nhất trong Python

Cho danh sách hộp, mỗi hộp là cặp [start, end] với start < end. Có thể nối hộp A vào hộp B nếu end_A == start_B. Tìm độ dài chuỗi hộp nối tiếp dài nhất.

Ví dụ

Đầu vào: [[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]

Chuỗi dài nhất: [1,2] → [2,4] → [4,5] → [5,6] → độ dài 4.

Thuật toán (Dynamic Programming với Dictionary)

1. Sắp xếp danh sách hộp theo start (và end phụ).
2. Dùng defaultdict(int) lưu dp[end] = độ dài chuỗi dài nhất kết thúc tại end.
3. Duyệt từng hộp (s, e):
   • dp[e] = max(dp[e], dp[s] + 1)
4. Kết quả là max(dp.values()).

Triển khai Python

import collections

class Solution:
    def solve(self, boxes):
        if not boxes:
            return 0
        boxes.sort()  # Sắp xếp theo start, rồi end
        dp = collections.defaultdict(int)
        for s, e in boxes:
            dp[e] = max(dp[e], dp[s] + 1)
        return max(dp.values())

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

Độ phức tạp

• Thời gian: O(n log n) do sắp xếp + O(n) duyệt.
• Không gian: O(n) cho dictionary dp.

Tương tự bài toán "Longest Chain of Pairs" / "Russian Doll Envelopes" biến thể.