पायथन में सभी फिल्मों को दिखाने के लिए आवश्यक न्यूनतम संख्या में मूवी थिएटर खोजने का कार्यक्रम

मान लीजिए कि हमारे पास अलग-अलग मूवी शो के लिए अंतराल की एक सूची है (उन्हें ओवरलैप किया जा सकता है), हमें सभी फिल्मों को दिखाने में सक्षम होने के लिए आवश्यक थिएटरों की न्यूनतम संख्या का पता लगाना होगा।

इसलिए, यदि इनपुट अंतराल की तरह है =[[20, 65], [0, 40], [50, 140]], तो आउटपुट 2 होगा, क्योंकि [20, 65] और [0, 40] अतिव्यापी हैं . [20, 65] और [50, 140] भी अतिव्यापी हैं लेकिन [0, 40] और [50, 140] नहीं हैं। इसलिए हमें 2 थिएटर चाहिए।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• t:=एक नई सूची
• प्रत्येक अंतराल के लिए [ए, बी] अंतराल में, करते हैं
  • t के अंत में [a, 1] डालें
  • टी के अंत में [बी, -1] डालें
• उत्तर:=0, गिनती:=0
• प्रत्येक जोड़ी (x, d) के लिए t क्रमबद्ध रूप में, do
  • गिनती:=गिनती + घ
  • उत्तर :=अधिकतम उत्तर और गणना
• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण कोड

class Solution:
   def solve(self, intervals):
      t = []
      for a, b in intervals:
         t.append((a, 1))
         t.append((b, -1))
         ans = count = 0
         for x, d in sorted(t):
            count += d
            ans = max(ans, count)
         return ans

ob = Solution()
intervals = [[20, 65],[0, 40],[50, 140]]
print(ob.solve(intervals))

इनपुट

[[20, 65],[0, 40],[50, 140]]

आउटपुट

2