পাইথনে সব সিনেমা প্রদর্শনের জন্য ন্যূনতম হলে সংখ্যা বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে বিভিন্ন সিনেমার শোয়ের ইন্টারভালের একটি তালিকা আছে (এরা ওভারল্যাপ করতে পারে)। আমাদের কাজ হল সব সিনেমা প্রদর্শন করতে পারার জন্য ন্যূনতম কতটি হলে প্রয়োজন তা বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয় intervals = [[20, 65],[0, 40],[50, 140]], তবে আউটপুট হবে 2, কারণ [20, 65] এবং [0, 40] ওভারল্যাপ করছে। [20, 65] এবং [50, 140] ও ওভারল্যাপ করছে কিন্তু [0, 40] এবং [50, 140] ওভারল্যাপ করছে না। তাই আমাদের ২টি হলে প্রয়োজন।

• 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