程序:在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