请教一道overlapping interval的题目

题目是这样子的：
Given a list of intervals sorted by start point in ascending order,  and an interval A, return if the interval A overlaps with any intervals in the list.

我想请教一下，如果list中的intervals可能本身就存在overlap，那么这个题目还可以使用binary search来做吗？

我目前的想法是，let A = [s, e], find the interval B = [s', e'] such that s' is the largest start that is <= e. 然后检查interval B是否和 interval A重合。我没有想清楚的地方是，如果B不和A重合，似乎并不能说明这个list里面就没有其他interval和A重合了。那么接下来应该怎么check呢？

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。

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

因为是按照start排序的，所以先找到the index where A should be inserted，然后先看index 是否和A overlap，如果不是再检查[0, index - 1]所有的interval

比如原来的list是[1, 100], [2,3], [6,7], [7,10]，A is [4,5]，首先用binary search找到insert index是2，然后看[6,7]和[4,5]不重合，然后再检查前面所有的

不知道有没有更好的办法

感觉只能把这之前的所有interval都检查一遍了。

我的想法是找到第一个end time比A的start time小的interval的index，称为idx1
找到第一个start time比A的end time大的interval的index, 称为idx2，
然后检查(idx1i,dx2)中间的interval和A有没有重合的


补充内容 (2021-1-26 06:11):
因为end无序 所以没办法binary search 我的想法是从idx2开始往前遍历比较interval是否重合 直到某个interval的end time 小于A的interval的start time就可以停止

看起来就是经典的interval题，应该是对start和end分别用binary search

你毛毛啊 发表于 2021-1-26 02:57
看起来就是经典的interval题，应该是对start和end分别用binary search

end不是有序的，怎么对end做binary search？

zli 发表于 2021-01-25 12:08:46
end不是有序的，怎么对end做binary search？

对头。不可以。

zli 发表于 2021-1-26 04:08
因为是按照start排序的，所以先找到the index where A should be inserted，然后先看index 是否和A overlap ...

嗯嗯非常感谢！我感觉这种方法的话binary search能减少一些需要iterate的intervals，但在worst case的时候还是O(n)的对吗？

不知道小帅 发表于 2021-1-26 00:49
感觉只能把这之前的所有interval都检查一遍了。

嗯嗯我也想了好久然后但是感觉好像只能强行扫一遍T_T

你毛毛啊 发表于 2021-1-26 02:57
看起来就是经典的interval题，应该是对start和end分别用binary search

谢谢！但是即使end也被sort过，可以binary search，应该怎么把两个集合intersect到一起呢？感觉求两个集合的intersection的操作也是O(n)的呀？这样和brute force直接扫一遍的时间复杂度似乎是一样的T_T