ধরুন আমাদের কাছে rect নামে একটি অ্যারে আছে যেখানে rect[i]-এ দুটি উপাদান রয়েছে [len_i, wid_i], যেখানে len_i এবং wid_i যথাক্রমে ith আয়তক্ষেত্রের দৈর্ঘ্য এবং প্রস্থকে প্রতিনিধিত্ব করছে। এখন আমরা ith আয়তক্ষেত্র কেটে একটি বর্গক্ষেত্র তৈরি করতে পারি যার পাশের দৈর্ঘ্য k হয় যদি k <=lenn_i এবং k <=wid_i উভয়ই হয়। সুতরাং উদাহরণস্বরূপ, যদি আমাদের একটি আয়তক্ষেত্র [4,6] থাকে, তাহলে আমরা এটিকে কাটতে পারি একটি বর্গক্ষেত্র যার বাহুর দৈর্ঘ্য সর্বাধিক 4। এখন বিবেচনা করুন ম্যাক্সলেন নামক একটি প্যারামিটারটি সবচেয়ে বড় বর্গক্ষেত্রের পাশের দৈর্ঘ্য যা আমরা পেতে পারি। প্রদত্ত আয়তক্ষেত্রগুলির যেকোনো একটি থেকে। আমাদের আয়তক্ষেত্রের সংখ্যা খুঁজে বের করতে হবে যেগুলো আমরা maxLen এর পাশের দৈর্ঘ্য দিয়ে একটি বর্গক্ষেত্র তৈরি করতে পারি।
সুতরাং, যদি ইনপুটটি rect =[[6,9],[4,10],[6,13],[17,6]] এর মত হয়, তাহলে আউটপুট হবে 3 কারণ আমরা বাহুর বৃহত্তম বর্গ পেতে পারি [ 6, 4, 6, 6], তাই তিনটি আয়তক্ষেত্র রয়েছে যা বৃহত্তম।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
m :=একটি নতুন তালিকা
-
প্রতিটি r রেক্টের জন্য, করুন
-
m
এর শেষে ন্যূনতম r সন্নিবেশ করান
-
-
গণনা (সর্বোচ্চ মি) m এ উপস্থিত এবং ফেরত
উদাহরণ (পাইথন)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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))
ইনপুট
[[6,9],[4,10],[6,13],[17,6]]
আউটপুট
3