Kiểm tra sắp xếp hình chữ nhật theo chiều rộng không tăng (Python)

Bài toán: Cho danh sách hình chữ nhật [length, breadth]. Có thể xoay 90° (hoán đổi length/breadth). Kiểm tra có sắp xếp được sao cho chiều rộng (breadth) không tăng dần không.

Thuật toán Greedy

Duyệt từ hình chữ nhật đầu tiên đến cuối. Với mỗi hình, chọn orientation (xoay hoặc không) sao cho breadth ≤ breadth trước đó, và breadth lớn nhất có thể (để dư không gian cho các hình sau).

Triển khai Python

def solve(rects):
    max_allowed = float('inf')  # breadth tối đa cho phép
    for l, b in rects:
        # Thử orientation cho breadth lớn nhất nhưng ≤ max_allowed
        candidates = []
        if l <= max_allowed:
            candidates.append(l)
        if b <= max_allowed:
            candidates.append(b)
        if not candidates:
            return False
        max_allowed = max(candidates)  # Chọn breadth lớn nhất có thể
    return True

# Test
print(solve([[4, 5], [5, 7], [4, 6]]))  # True: breadths [5, 5, 4] (xoay 2,3)
# Rect1: 4x5 → breadth=5 (max_allowed=inf→5)
# Rect2: 5x7 → breadth=5 (xoay: 7>5 không được, 5≤5 OK)
# Rect3: 4x6 → breadth=4 (xoay: 6>5 không được, 4≤5 OK)
print(solve([[3, 4], [5, 5]]))          # False

Kết quả

True

Giải thích

• Biến max_allowed theo dõi breadth tối đa cho phép của hình hiện tại (phải ≤ breadth hình trước).
• Với mỗi hình, xem xét 2 orientation: breadth = length hoặc breadth. Chọn giá trị lớn nhất ≤ max_allowed.
• Nếu không có orientation nào thỏa mãn → False.
• Greedy đúng vì chọn breadth lớn nhất để dư "không gian" tối đa cho các hình sau.
• Độ phức tạp: O(n) time, O(1) space.