搜索间隔列表的时间复杂性
设a是interval [a.start, a.end]，其中a.start和a.end是实数，例如0 <= a.start < a.end <= 1。
两个这样的间隔a和b 相交如果a.start < b.start < a.end或b.start <= a.start < b.end
让As成为非相交区间a_0, a_1, ..., a_n的排序列表，这样a_i就不会为i < j交叉a_j和a_i.start < a_j.start。
给定区间b，在As中确定b相交的第一个区间和最后一个区间(或者没有找到交叉口)。即:如果可能，请查找i和j，以便b与a_i和a_j相交，而不是a_{i-1}或a_{j+1}
我用一个改进的二进制搜索(在最坏的情况下是O(N))来解决这个问题，所以我的直觉是，这是一个lg(n)问题，但是我不知道我是否有最好的算法。
回答 1
Stack Overflow用户
发布于 2017-06-28 20:23:45
因为您有一个排序的非相交区间列表，所以您知道每个间隔在下一个间隔开始之前结束，并且您也可以将此列表视为间隔开始点的排序列表，或区间结束点的排序列表。
我认为您可以在排序的区间端点列表上使用二进制搜索来找到最小的区间端点，它在O(log )最坏的情况下至少与b.start一样大，这是与b相交的第一个区间(如果任何区间与b相交的话)。类似地，与b相交的最后一个间隔的最大起始点不大于b.end，如果任何间隔与b相交的话。
要找到与目标至少一样大的最小点，请查看可能解决方案范围中间的点(按可能解决方案的数量，而不是按位置)。如果这一点至少和目标一样大，那么可能的解决方案的范围从这一点延伸到左边，并包括这一点。如果这一点不像目标那么大，那么可能的解决方案的范围就从那一点之后延伸到右边。在这两种情况下，您已经将可能的解决方案的数量减少了大约一半，因此您有最坏的情况O(log )。
https://stackoverflow.com/questions/44814684
复制相似问题
腾讯云开发者
