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

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

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

समाधान दृष्टिकोण

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

• t := एक नई सूची
• प्रत्येक अंतराल [a, b] के लिए intervals में:
  • [a, 1] को t के अंत में डालें
  • [b, -1] को t के अंत में डालें
• ans := 0, count := 0
• प्रत्येक जोड़ी (x, d) के लिए t के सॉर्टेड रूप में:
  • count := count + d
  • ans := max(ans, count)
• ans लौटाएं

उदाहरण कोड

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