Chương trình tìm số hộp tối đa lồng vào nhau trong Python

Cho danh sách hộp, mỗi hàng là [width, height]. Hộp A lồng vào hộp B nếu width_A < width_B VÀ height_A < height_B. Tìm chuỗi lồng hộp dài nhất (max số hộp).

Ví dụ: [[12,12],[10,10],[6,6],[5,10]] → output 3 ([6,6] → [10,10] → [12,12]).

Quan sát: Đây là bài toán LIS (Longest Increasing Subsequence) 2 chiều. Sắp xếp theo width tăng, height giảm (để tránh chọn 2 hộp cùng width). Sau đó tìm LIS trên height.

Thuật toán:

• Sắp xếp: key=lambda x: (x[0], -x[1]) (width tăng, height giảm)
• Tìm LIS trên mảng height dùng binary search (O(n log n))
• Duy trì mảng heights: heights[len] = height nhỏ nhất kết thúc LIS độ dài len
• Với mỗi cur_h: tìm index = upper_bound(heights, cur_h) (vị trí chèn đầu tiên > cur_h)
• Cập nhật heights[index] = cur_h, res = max(res, index)

Triển khai

class Solution:
    def solve(self, matrix):
        # Sắp xếp width tăng, height giảm
        matrix = sorted(matrix, key=lambda x: (x[0], -x[1]))
        n = len(matrix)
        
        # heights[i] = height nhỏ nhất kết thúc LIS độ dài i
        heights = [float("inf")] * (n + 1)
        heights[0] = float("-inf")
        res = 0
        
        for box in matrix:
            cur_w, cur_h = box
            index = self.insert_index(heights, cur_h)
            if heights[index] >= cur_h:
                heights[index] = cur_h
            res = max(res, index)
        return res
    
    def insert_index(self, arr, this_h):
        """Binary search: tìm vị trí chèn (upper bound)"""
        l, r = 0, len(arr) - 1
        res = 0
        while l <= r:
            m = l + (r - l) // 2
            cur_h = arr[m]
            if cur_h < this_h:
                res = m
                l = m + 1
            else:
                r = m - 1
        return res + 1

ob = Solution()
matrix = [[12, 12], [10, 10], [6, 6], [5, 10]]
print(ob.solve(matrix))

Đầu vào

[[12, 12], [10, 10], [6, 6], [5, 10]]

Đầu ra

3

Giải thích: Sắp xếp width tăng, height giảm đảm bảo: width khác nhau → thứ tự cố định; width cùng → height giảm → chỉ chọn được tối đa 1 hộp (vì LIS height tăng bắt buộc height tăng chặt). Binary search tìm upper_bound trong mảng heights đơn điệu tăng. Phức tạp O(n log n).