狗狗太阳谷跪经

foryousee 发表于 2018-11-8 10:38
是一个意思，先排序，按照meeting room解出所有的rooms，然后根据rooms含有的interval排序

按meeting room解出来不一定是最优解吧？比如一个序列(1,3) (2,10) (4,50)  (8,11) (12,13) (14,15)
按meeting room的heap解法应该是
(1,3) (4,50)
(2,10) (12,13)
(8,11) (14,15)
不是最优解啊。我感觉像一个graph求最大clique的题…

补充内容 (2018-11-11 03:05):
或者我觉得可以先求出来需要几个屋子，然后用DFS暴力求解

nhqgoal 发表于 2018-11-8 10:13
咱俩对题意的理解好像不一样？ 我的理解是 输入是一堆intervals， 然后要求给每个interval assign level  ...

不太理解第一题究竟要求什么，是给出一系列interval（已经assign好level了？），判断当前interval assignment是否符合楼主说的越低越好的原则？

还是说assignment没预先assign好，由我们来写算法return最优level分配方式？

wtcupup 发表于 2018-11-8 09:35
最后一轮用 一个k size 的 BST maintain sorted data， 用一个queue maintain最近的k， when queue size bi ...

不太明白是不是这个意思：maintain一个k大小的窗口，用map（即BST）记录k这个窗口中的值，用一个变量sum维持这个窗口中的和，每次计算时从sum中去掉前后5%的值， 并从k这个窗口（也即当前窗口包含元素数目）中去掉对应的前后5%元素的个数，以此计算中间90%平均值？时间复杂度O(nk）。