程序:在Python中找到显示所有电影所需的最少电影院数量

程序:在Python中找到显示所有电影所需的最少电影院数量

假设我们有一个不同电影播放时间间隔的列表(它们可能重叠),我们必须找出所需的最少电影院数量,以便能够显示所有电影。

因此,如果输入为intervals = [[20,65],[0,40],[50,140]],则输出将为2,因为[20,65]和[0,40]重叠。[20,65]和[50,140]也重叠,但[0,40]和[50,140]没有重叠。因此我们需要2个电影院。

要解决这个问题,我们将遵循以下步骤:

  • t:一个新列表
  • 对于intervals中的每个区间[a,b],执行以下操作:
    • 在t的末尾插入[a,1]
    • 在t的末尾插入[b,-1]
  • ans:= 0,count:= 0
  • 对于t中以排序形式出现的每对(x,d),执行以下操作:
    • count:= count + d
    • ans:= 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程