ตรวจสอบว่าเรียงสี่เหลี่ยมผืนผ้าให้ Breadth ไม่เพิ่มได้หรือไม่ (หมุนได้) ด้วย Python

มี List สี่เหลี่ยม [Length, Breadth] หมุน 90 องศาได้ (สลับ L<->B) ต้องเช็คว่าเรียงให้ Breadth Non-increasing ได้หรือไม่

เช่น Input rects = [[4, 5], [5, 7], [4, 6]] Output True หมุน 2 ตัวท้าย Breadths: [5,5,4]

ขั้นตอนแก้ (Greedy):

• m = ค่ามาก (Infinity)
• แต่ละ Rect: ถ้า max(L,B) <= m ใช้ max; else if min(L,B) <= m ใช้ min; else False
• อัพเดท m = ค่าที่เลือก

ตัวอย่างโค้ด

def solve(rect):
    m = 99999
    for i in range(len(rect)):
        if max(rect[i][0], rect[i][1]) <= m:
            m = max(rect[i][0], rect[i][1])
        elif min(rect[i][0], rect[i][1]) <= m:
            m = min(rect[i][0], rect[i][1])
        else:
            return False
    return True

rects = [[4, 5], [5, 7], [4, 6]]
print(solve(rects))

Input

[[4, 5], [5, 7], [4, 6]]

Output

True