首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  算法

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

  •  
  •   duohedianshuihao · 2018-08-16 12:06:48 +08:00 · 1097 次点击
    这是一个创建于 477 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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 重叠。问题是在整个时间范围内,哪个时刻需要的会议室数目最多,最大数目是多少?

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

    查到了 好像用扫描线算法

    2 回复  |  直到 2018-08-16 12:57:22 +08:00
        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 最大就可以了
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2741 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 36ms · UTC 10:56 · PVG 18:56 · LAX 02:56 · JFK 05:56
    ♥ Do have faith in what you're doing.