ตรวจสอบว่าเป็นไปได้หรือไม่ที่จะจัดเรียงสี่เหลี่ยมผืนผ้าใหม่โดยเรียงลำดับความกว้างในPython

สมมติว่าเรามีรายการรูปสี่เหลี่ยมผืนผ้าที่แสดงโดยใช้ความยาวและความกว้าง เราสามารถหมุนสี่เหลี่ยมผืนผ้าใดๆ ก็ได้ 90 องศา ดังนั้นหลังจากหมุนแล้ว ความกว้างจะกลายเป็นความยาวและในทางกลับกัน เราต้องตรวจสอบว่าเราสามารถจัดเรียงสี่เหลี่ยมในลำดับความกว้างที่ไม่เพิ่มขึ้นได้หรือไม่

ดังนั้น ถ้าอินพุตเหมือน rects =[[4, 5], [5, 7], [4, 6]] เอาต์พุตจะเป็น True ตามความกว้าง [5,7,6] ตอนนี้ถ้าเราหมุน สี่เหลี่ยมสองรูปสุดท้าย ความกว้างจะเป็น [5,5,4] ซึ่งไม่เพิ่มขึ้น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=99999
• สำหรับ i ในช่วง 0 ถึงขนาดของ rect ให้ทำ
  • ถ้าความยาวและความกว้างสูงสุดของสี่เหลี่ยมผืนผ้า ith <=m แล้ว
    • m :=ความยาวและความกว้างสูงสุดของสี่เหลี่ยมผืนผ้า ith
  • มิฉะนั้น เมื่อความยาวและความกว้างต่ำสุดของสี่เหลี่ยมผืนผ้า ith <=m
    • m :=ความยาวและความกว้างต่ำสุดของสี่เหลี่ยมผืนผ้า ith
  • มิฉะนั้น
    • คืนค่าเท็จ
• คืนค่า True

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

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

ผลลัพธ์

True