会议室 follow up

lintcode 919. 会议室,

只有一个会议室
follow up, 假设很多很多会议，使用什么数据结构存储已安排的会议，要求插入和查询都要快

不晓得是不是要求O(1) 的插入和查询, 查询怎么也得扫描提下, 感觉 O(1) 有点难, 或者用minheap,

欢迎大家讨论

大家别光点赞啊，这个是面筋题啊

我觉得用HashMap就可以吧

becoo 发表于 2019/04/15 12:38:35
我觉得用HashMap就可以吧

插入是没问题，但是怎么检索一个人会议室是否可行，得遍历整个key啊

如果是“只有一个会议室，很多很多会议”的话，难道不是merge sorted intervals的思路。
然后用O(Log N)来查询是否该区间已经被占。如果没有被占，那么可以插入。否则这个meeting 请求会被拒绝。
插入是O(Log N)。更好一点，如果相邻，把插入的，和其前面和后面的三个intervals全部merge。

如果就是楼顶列出的这些条件，O（1）我认为做不出来。

14417335 发表于 2019-4-15 20:56
如果是“只有一个会议室，很多很多会议”的话，难道不是merge sorted intervals的思路。
然后用O(Log N)来 ...

感觉你说的是对的, 光想着用扫描线了,狭隘了,狭隘了

gui59106375 发表于 2019-4-15 12:57
插入是没问题，但是怎么检索一个人会议室是否可行，得遍历整个key啊

释放meeting room的时候，把room number 记录到hashset里面去啊。。。这样可以直接check啊