Hedvig电面，二面Interval至今不会

一面：

Merge K Sorted Arrays，秒了。问除了用PriorityQueue还能用什么方法，我说两两Merge。

二面：

和之前某人Onsite的面经很像:

“有一堆interval 要保证用o(1)找到哪些interval包含某个点 这里空间复杂度不能和interval的长度有关, 楼主提了N种方案 最后还是借鉴了 Range Addition 的思路 大哥说我写的这个就是他们现在用的"

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

">因为delete/insert并不是重点，于是我就用一个list存interval，每次insert后sort一下(sort by start)，然后通过二分法找到第一个start，然后往后找。小哥说我这样worst case是O(N)的。于是我说，那我再create另外一个List，按照end排序。每次我先从按start的排序里找到不符合，踢掉，再从按end排序的List里找不符合的，踢掉。不过感觉思路更不对了。。总之小哥不太满意我的答案。。不过还是感觉给我2次面试机会。。

二面至今都没出来有啥好的解法，之前onsite的那位说可以用addition range O(1)做出来。不知道能求大神解答么？感谢！

mark一下同求大神解答，好难