Chương trình tìm số hình chữ nhật có thể tạo thành hình vuông lớn nhất trong Python

Giả sử chúng ta có một mảng có tên là direct trong đó direct [i] có hai phần tử [len_i, wid_i], trong đó len_i và wid_i lần lượt đại diện cho chiều dài và chiều rộng của hình chữ nhật thứ i. Bây giờ chúng ta có thể cắt hình chữ nhật thứ i để tạo thành một hình vuông có độ dài cạnh là k nếu cả k <=lenn_i và k <=wid_i. Vì vậy, ví dụ, nếu chúng ta có một hình chữ nhật [4,6], thì chúng ta có thể cắt nó để có được một hình vuông có độ dài cạnh tối đa là 4. Bây giờ hãy coi một tham số gọi là maxLen là độ dài cạnh của hình vuông lớn nhất mà chúng ta có thể nhận được từ bất kỳ hình chữ nhật nào trong số các hình chữ nhật đã cho. Chúng ta phải tìm số hình chữ nhật mà chúng ta có thể tạo thành một hình vuông có độ dài cạnh là maxLen.

Vì vậy, nếu đầu vào giống như direct =[[6,9], [4,10], [6,13], [17,6]], thì đầu ra sẽ là 3 vì chúng ta có thể nhận được hình vuông lớn nhất của các cạnh [ 6, 4, 6, 6], vì vậy có ba hình chữ nhật là lớn nhất.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=một danh sách mới

• đối với mỗi r trong trực tràng, thực hiện

  • chèn tối thiểu r vào cuối m

• đếm (tối đa m) hiện diện trong m và trả về

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(rect):
   m = []
   for r in rect:
      m.append(min(r))

   return m.count(max(m))

rect = [[6,9],[4,10],[6,13],[17,6]]
print(solve(rect))

Đầu vào

[[6,9],[4,10],[6,13],[17,6]]

Đầu ra

3