请教一个类似 leetcode meeting room 的问题

[duohedianshuihao]

class Schedule():
  def __init__(self, start, end, rooms):
    self.start = start
    self.end = end
    self.rooms = rooms

schedule_list = [Schedule(1, 4, 2), Schedule(2, 6, 1), ...]

Schedule 是会议室使用的起始时间，终止时间和会议室需要的数目。某个时间点可能会有多个 Schedule 重叠。问题是在整个时间范围内，哪个时刻需要的会议室数目最多，最大数目是多少？

~~有没有什么好的思路，麻烦讲一下，谢谢!~~

查到了 好像用扫描线算法

[rabbbit]

创建一个长度为 24 数组,用 0 填充,对应一天的时间
遍历 schedule_list,累加对应时间所需会议室数量
例如
Schedule(1, 4, 2) -> [0, 2, 2, 2, 2, 0, 0, ...]
Schedule(2, 6, 1) -> [0, 2, 3, 3, 3, 1, 1, ...]
最大数就是某时刻最多会议室数量,时间复杂度(n^2)

[rabbbit]

又想到一种解法
维护两个数组,一个表示开始时间,另一个表示结束时间
例如
start = [1, 1, 2, ...]
end = [4, 4, 6, ...]
按从小到大排序两个数组

然后维护三个变量 i=0 j =0 表示数组 start end 的下标,count = 0 表示当前使用会议室数
如果 start[i] < end[j], 会议开始 count++ i++
如果 start[i] > end[j], 会议结束 count-- j++
如果 start[i] === end[j], 同时有会议开始结束 i++ j++
然后判断哪个时间点 count 最大就可以了