寻找在python中放映所有电影所需的最少电影院数量的程序

假设我们有不同电影放映的间隔列表（它们可以重叠），我们必须找到能够放映所有电影所需的最少影院数量。

因此，如果输入类似于区间 = [[20, 65],[0, 40],[50, 140]]，那么输出将为 2，因为 [20, 65] 和 [0, 40] 是重叠的. [20, 65] 和 [50, 140] 也重叠，但 [0, 40] 和 [50, 140] 不是。所以我们需要2个剧院。

为了解决这个问题，我们将按照以下步骤操作：

• t := 一个新列表

• 对于间隔中的每个区间 [a, b]，做

• 在 t 的末尾插入 [a, 1]

• 在 t 的末尾插入 [b, -1]

• 答案：= 0，计数：= 0

• 对于排序形式的 t 中的每一对 (x, d)，做

• 计数 := 计数 + d

• ans := ans 和 count 的最大值

• 返回答案

让我们看下面的实现来更好地理解：

示例代码

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