假设[a,b]表示从a到b的实线上的间隔,a <b,包括(即,[a,b] =所有x的集合,使得a <= x <= b).另外,如果[a,b]和[c,d]共享任何x使得x在[a,b]和[c,d]中都是'重叠'.
给定一个区间列表,([x1,y1],[x2,y2],...),找到与[x,y]重叠的所有这些区间的最有效方法是什么？
显然,我可以尝试每个并在O(n)中得到它.但是我想知道我是否能够以一种聪明的方式对间隔列表进行排序,我可以通过二分搜索在O(log N)中找到/ one /重叠项目,然后从列表中的那个位置"环顾四周"找到所有重叠的间隔.但是,如何对间隔进行排序以使这种策略有效？
请注意,列表项中的元素之间可能存在重叠,这使得这很难.
我已经通过左边,右端,中间的间隔排序来尝试它,但似乎都没有导致详尽的搜索.
救命？
algorithm ×1