在间隔列表中搜索间隔重叠? [英] search for interval overlap in list of intervals?

问题描述

说[a,b]表示a到b的实线上的区间，a

Say [a,b] represents the interval on the real line from a to b, a < b, inclusive (ie, [a,b] = set of all x such that a<=x<=b). Also, say [a,b] and [c,d] are 'overlapping' if they share any x such that x is in both [a,b] and [c,d].

给定一个区间列表 ([x1,y1],[x2,y2],...)，找到所有与 [x,y] 重叠的区间的最有效方法是什么?

Given a list of intervals, ([x1,y1],[x2,y2],...), what is the most efficient way to find all such intervals that overlap with [x,y]?

显然，我可以尝试每一个并在 O(n) 中得到它.但是我想知道是否可以以某种巧妙的方式对间隔列表进行排序，我可以通过二分搜索在 O(log N) 中找到/one/重叠项，然后从列表中的那个位置环顾四周"以找到所有重叠间隔.但是，如何对间隔进行排序以使这种策略有效?

Obviously, I can try each and get it in O(n). But I was wondering if I could sort the list of intervals in some clever way, I could find /one/ overlapping item in O(log N) via a binary search, and then 'look around' from that position in the list to find all overlapping intervals. However, how do I sort intervals such that such a strategy would work?

请注意，列表项本身中的元素之间可能存在重叠，这就是为什么这很困难.

Note that there may be overlaps between elements in the list items itself, which is what makes this hard.

我尝试过按左端、右端、中间对间隔进行排序，但似乎没有一个会导致彻底搜索.

I've tried it by sorting intervals by their left end, right end, middle, but none seem to lead to an exhaustive search.

帮助?

推荐答案

[a, b] 与 [x, y] 重叠且仅当 b > x 且 a <是的按第一个元素对间隔进行排序可以得到与日志时间中第一个条件匹配的间隔.按最后一个元素对间隔进行排序为您提供与日志时间中的第二个条件匹配的间隔.取结果集的交集.

[a, b] overlaps with [x, y] iff b > x and a < y. Sorting intervals by their first elements gives you intervals matching the first condition in log time. Sorting intervals by their last elements gives you intervals matching the second condition in log time. Take the intersections of the resulting sets.

这篇关于在间隔列表中搜索间隔重叠?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！