这是一个创建于 2615 天前的主题，其中的信息可能已经有所发展或是发生改变。
class Schedule(): def __init__(self, start, end, rooms): self.start = start self.end = end self.rooms = rooms schedule_list = [Scheule(1, 4, 2), Schedule(2, 6, 1), ...] Schedule 是会议室使用的起始时间，终止时间和会议室需要的数目。某个时间点可能会有多个 Schedule 重叠。问题是在整个时间范围内，哪个时刻需要的会议室数目最多，最大数目是多少？
~~有没有什么好的思路，麻烦讲一下，谢谢!~~
查到了 好像用扫描线算法
 | 1 rabbbit 2018-08-16 12:21:53 +08:00 创建一个长度为 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 2018-08-16 12:57:22 +08:00 又想到一种解法 维护两个数组,一个表示开始时间,另一个表示结束时间 例如 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