请教一道overlapping interval的题目

ForrestGump 发表于 2021-1-26 01:46
我的想法是找到第一个end time比A的start time小的interval的index，称为idx1
找到第一个start time比A的e ...

谢谢！我在想即使有另一个list是按照end sort的，我们在这个list里面找到的idx好像跟前面的根据start sort的list的index并不是对应的吧？这样感觉没法直接找[idx1, idx2]之间的interval

highsprite 发表于 2021-1-26 06:30
谢谢！但是即使end也被sort过，可以binary search，应该怎么把两个集合intersect到一起呢？感觉求两个集 ...

你说的对的，如果intervals本身就有overlapping，binary search不能直接找出overlapping的区间。我的想法是用binary search把不可能overlapping的intervals去掉，最后剩下的就是要求的intervals。具体implementation可以只用一集合，可以用各个interval的start和end建立一个id，binary search排除完，剩下的就是有overlapping的intervals。