基于time slot的会议室/停车场设计

我看到设计题里有一类是基于time slot的搜索设计，没什么思路，请教地里大牛

比如好几个会议室组成的会议室系统，给一个指定appointment时间，如何快速找到一个available的会议室？时间复杂度多少？

一个停车场，每个车位分24小时接受booking，用户可以online booking，也可以直接开车到停车场booking，如何快速找到available car spot？
车子离开的时候，如何快速释放car spot？

可能比较细节，还请大家给个指点，谢谢

第一个题因为需要在预约时定下哪个meeting room归你。想不出来什么更好的优化。只能是 O(N Log K) 每个meeting room的登记记录都扫一下。

第二题，假设一个大parking structure也分成若干层。维护每个sublot的在每天的availability的记录。预约的时候只需要寻找sublot从预约区间开始处有无连续的k天都有位子。同时update这个availability。这样超过了就不应该再放人进来。真正开车来的那天（无论是预约后开车来还是无预约开车来）到指定的sublot里找一个lot就可以。（维护当下busy lot和available lot）

如果是OOD的话，可以用stack，一个available stack, 车子来到时候，如果stack不为空的话，直接pop,时间复杂度常量; 一个车子离开的时候，直接push回stack. 如果系统设计的时候，你可能需要用两个数据表，然后把available spot那个表load在cache中；

前提：假设每天会议室数据都清0。
会议系统: 最原始做法，
创建一个range class，包含开始和结束时间。 假设会议室ID由0到n-1,创建一个会议室List，value 是 所有该会议室被占用时间段。指定某个时间就遍历这个列表，找个相应时间空闲的会议室。当然，这种做法效率太低，不推荐。

优化做法：
其实我也不知道，现在能想到的做法（假设会议时间以分钟为单位),建立一个map<integer, List<Integer>>, 将一天分成3600分钟，一个会议室被用，就找到相应的分钟的可以（当然，会很多，比如半小时，就是有30个key），把该会议室加到value的列表中。会议结束后，再找到相应的keys，从list里面去掉。
时间复杂度：
get: size of all meetings
add meeting: length of the meeting time
remove meeting: length of the meeting time

呵呵，抛砖引玉呀：）


补充内容 (2019-4-1 03:09):
发现不对劲，预订会议不仅仅只有开始时间，还有结束时间。呵呵，周末，脑细胞不够用了:(

pxu 发表于 2019-4-1 03:07
前提：假设每天会议室数据都清0。
会议系统: 最原始做法，
创建一个range class，包含开始和结束时间。  ...

潜意识里感觉需要用线段树这种高级数据结构去解决，不过我懒得学了

pxu 发表于 2019-4-1 03:14
潜意识里感觉需要用线段树这种高级数据结构去解决，不过我懒得学了

第一题应该就是前面楼说的O(n*logk), 不知道有没有更好的