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 重叠。问题是在整个时间范围内，哪个时刻需要的会议室数目最多，最大数目是多少？
~~有没有什么好的思路，麻烦讲一下，谢谢!~~
查到了 好像用扫描线算法
 |
1
rabbbit Aug 16, 2018
创建一个长度为 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) |
|
2
rabbbit Aug 16, 2018
又想到一种解法
维护两个数组,一个表示开始时间,另一个表示结束时间 例如 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 最大就可以了 |
Select Language