Python - 移除重叠的列表

Question

假设我有一个带有索引的列表，索引格式为[[start，end]，[start1，end1]，[start2，end2]]。

例如：

[[0,133]，[78,100]，[25,30]].

如何检查这些列表之间的重叠并每次删除长度更长的列表呢？

>>> list = [[0, 133], [78, 100], [25, 30]]
>>> foo(list)
[[78, 100], [25, 30]]

这是我到目前为止所尝试的:

def cleanup_list(list):
    i = 0
    c = 0
    x = list[:]
    end = len(x)
    while i < end-1:
        for n in range(x[i][0], x[i][1]):
            if n in range(x[i+1][0], x[i+1][1]):
                list.remove(max(x[i], x[i+1]))
        i +=1
    return list

但是除了有点复杂外，它还不能正常工作：

 >>>cleanup_list([[0,100],[9,10],[12,90]])
 [[0, 100], [12, 90]]

需要帮助，感激不尽！

编辑：

其他示例包括：

>>>a = [[0, 100], [4, 20], [30, 35], [30, 78]]
>>>foo(a)
[[4, 20], [30, 35]]

>>>b = [[30, 70], [25, 40]]
>>>foo(b)
[[25, 40]]

我基本上正在尝试删除所有与另一个列表重叠的最长列表。在这种情况下，我不必担心列表长度相等的问题。

谢谢！！

- user2338068

---

如果存在三个或更多的重叠，我担心这将成为一个定义不清的问题。 - wim

抱歉，我不太确定你的意思是什么？ - user2338068

@user2338068：你能展示一些样例输入/输出组合吗？ - Ayush

没有重叠的列表将具有相同的长度。如果有多个重叠，我会尝试返回最短长度的列表。 - user2338068

是的，那正是它。 - user2338068

Answer 1

有一种 O(n*log n) 的算法，可以从列表中删除最少数量的区间，使剩下的区间不重叠：

def maximize_nonoverlapping_count(intervals):
    # sort by the end-point
    L = sorted(intervals, key=lambda (start, end): (end, (end - start)),
               reverse=True) # O(n*logn)
    iv = build_interval_tree(intervals) # O(n*log n)
    result = []
    while L: # until there are intervals left to consider
        # pop the interval with the smallest end-point, keep it in the result
        result.append(L.pop()) # O(1)
        # remove intervals that overlap with the popped interval
        overlapping_intervals = iv.pop(result[-1]) # O(log n + m)
        remove(overlapping_intervals, from_=L) 
    return result

它应该产生以下结果:

f = maximize_nonoverlapping_count
assert f([[0, 133], [78, 100], [25, 30]]) == [[25, 30], [78, 100]]
assert f([[0,100],[9,10],[12,90]]) == [[9,10], [12, 90]]
assert f([[0, 100], [4, 20], [30, 35], [30, 78]]) == [[4, 20], [30, 35]]
assert f([[30, 70], [25, 40]]) == [[25, 40]]

这需要一种数据结构，可以在O(log n + m)的时间内查找与给定区间重叠的所有区间，例如IntervalTree。有可以从Python中使用的实现，例如quicksect.py，请参见快速区间交集方法以获取示例用法。

---

这是以上算法的基于quicksect的O(n**2)实现：

from quicksect import IntervalNode

class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.removed = False

def maximize_nonoverlapping_count(intervals):
    intervals = [Interval(start, end) for start, end in intervals]
    # sort by the end-point
    intervals.sort(key=lambda x: (x.end, (x.end - x.start)))   # O(n*log n)
    tree = build_interval_tree(intervals) # O(n*log n)
    result = []
    for smallest in intervals: # O(n) (without the loop body)
        # pop the interval with the smallest end-point, keep it in the result
        if smallest.removed:
            continue # skip removed nodes
        smallest.removed = True
        result.append([smallest.start, smallest.end]) # O(1)

        # remove (mark) intervals that overlap with the popped interval
        tree.intersect(smallest.start, smallest.end, # O(log n + m)
                       lambda x: setattr(x.other, 'removed', True))
    return result

def build_interval_tree(intervals):
    root = IntervalNode(intervals[0].start, intervals[0].end,
                        other=intervals[0])
    return reduce(lambda tree, x: tree.insert(x.start, x.end, other=x),
                  intervals[1:], root)

注意：由于该实现仅标记间隔为已删除状态，因此最坏情况下的时间复杂度为 O(n**2)。

例如，想象这样的输入：intervals，使得len(result) == len(intervals) / 3，且有len(intervals) / 2个区间跨越整个范围，则会调用tree.intersect() n/3次，每次调用都会执行x.other.removed = True至少n/2 次。总共执行操作次数为n*n/6：

n = 6
intervals = [[0, 100], [0, 100], [0, 100], [0, 10], [10, 20], [15, 40]])
result = [[0, 10], [10, 20]]

这是基于 banyan 的 O(n log n) 实现：

from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan

def maximize_nonoverlapping_count(intervals):
    # sort by the end-point O(n log n)
    sorted_intervals = SortedSet(intervals,
                                 key=lambda (start, end): (end, (end - start)))
    # build "interval" tree O(n log n)
    tree = SortedSet(intervals, updator=OverlappingIntervalsUpdator)
    result = []
    while sorted_intervals: # until there are intervals left to consider
        # pop the interval with the smallest end-point, keep it in the result
        result.append(sorted_intervals.pop()) # O(log n)

        # remove intervals that overlap with the popped interval
        overlapping_intervals = tree.overlap(result[-1]) # O(m log n)
        tree -= overlapping_intervals # O(m log n)
        sorted_intervals -= overlapping_intervals # O(m log n)
    return result

注意：该实现认为 [0, 10] 和 [10, 20] 区间是重叠的：

f = maximize_nonoverlapping_count
assert f([[0, 100], [0, 10], [11, 20], [15, 40]]) == [[0, 10] ,[11, 20]]
assert f([[0, 100], [0, 10], [10, 20], [15, 40]]) == [[0, 10] ,[15, 40]]

sorted_intervals 和 tree 可以合并：

from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan

def maximize_nonoverlapping_count(intervals):
    # build "interval" tree sorted by the end-point O(n log n)
    tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)),
                     updator=OverlappingIntervalsUpdator)
    result = []
    while tree: # until there are intervals left to consider
        # pop the interval with the smallest end-point, keep it in the result
        result.append(tree.pop()) # O(log n)

        # remove intervals that overlap with the popped interval
        overlapping_intervals = tree.overlap(result[-1]) # O(m log n)
        tree -= overlapping_intervals # O(m log n)
    return result

- jfs

---

非常感谢！我刚接触编程，所以有些东西有点困惑-但我会阅读你的链接。但是要澄清的是，build_interval_tree是一个类似于quicksect.py中的代码，我需要创建的函数吗？ - user2338068

@user2338068：我添加了一个基于quicksect的实现，展示它可能看起来像什么（如果您下载 quicksect.py 并将其放在与脚本相同的目录中，则可以运行它）。 - jfs

我已经添加了基于“榕树”（banyan）的O(n log n)实现（“榕树”不是纯Python，使用C++编写C扩展程序用于Python，因此可能会使安装更加困难）。 - jfs

很多东西现在超出了我的理解范围，但我会尽力去理解。谢谢，伙计，我非常感激。 - user2338068

Answer 2

这可能不是最快的解决方案，但非常详细和清晰 - 我想。

a = [[2,100], [4,10], [77,99], [38,39], [44,80], [69,70], [88, 90]]

# build ranges first
def expand(list):
    newList = []
    for r in list:
        newList.append(range(r[0], r[1] + 1))
    return newList


def compare(list):
    toBeDeleted = []
    for index1 in range(len(list)):
        for index2 in range(len(list)):
            if index1 == index2:
                # we dont want to compare ourselfs
                continue
            matches = [x for x in list[index1] if x in list[index2]]
            if len(matches) != 0: # do we have overlap?
                ## compare lengths and get rid of the longer one
                if   len(list[index1]) > len(list[index2]):
                    toBeDeleted.append(index1)
                    break
                elif len(list[index1]) < len(list[index2]):
                    toBeDeleted.append(index2)
    # distinct
    toBeDeleted = [ toBeDeleted[i] for i,x in enumerate(toBeDeleted) if x not in toBeDeleted[i+1:]] 
    print len(list)
    # remove items
    for i in toBeDeleted[::-1]:
        del list[i] 
    return list


print(compare(expand(a)))

- AlessandroEmm

---

这个解决方案可能会删除太多，即可能返回比保留的非重叠区间少的结果。这是不必要的O(n**4)。现在还不清楚distinct计算是否正确，你是指toBeDeleted = set(toBeDeleted)还是其他什么？list是内置名称，请避免将其用作变量名。 - jfs

你是对的：它不够快（特别是与你的相比），但在我看来更详细并且更易于维护。toBeDeleted = set(toBeDeleted) 执行的操作与我的迭代式一样，只是如果你不知道 set() 的话，它更为明显。也许我弄错了问题，但我没有注意到任何重叠移除。感谢你的意见！ - AlessandroEmm

请注意：

1. 这个解决方案不起作用：[[0, 10], [9, 12], [11, 20]] -> [[9, 10, 11, 12]]，而不是[[0, 10], [11, 20]]
2. 即使对于像len(a) == 100这样的小输入，如果它能够工作，它也会非常慢，这个解决方案需要~100**4（~100000000）次操作。很容易将其变为O(n ** 2)（~10000次操作），并且更易读（尽管我认为我的O(n log n)（~500次操作）版本（特别是基于单个SortedSet使用的banyan解决方案）比上述的O(n ** 4)解决方案更易读）。

- jfs

Answer 3

我认为你代码中的一个问题是它没有处理一个列表包含另一个列表的情况。例如，[0,100]包含[9,10]。当你在[0,100]循环n并且n进入[9,10]时，条件语句if n in range(x[i+1][0], x[i+1][1])会被触发。然后内置函数max将比较[0,100]和[9,10]，不幸的是，max将返回[9,10]，因为它比较列表中的第一个数字。因此，你删除了错误的元素。

我正在尝试另一种方法来实现你想要的效果。而不是操作列表本身，我创建一个新列表。如果符合我们的要求，则有条件地将新元素附加到它上面。

def cleanup_list(lists):
    ranges = []
    for l in lists:
        to_insert = True
        for i in ranges:
            r = range(i[0],i[1])
            # if l overlaps with i, but l does not contain i
            if l[0] in r or l[1] in r:
                if (l[1]-l[0]) < len(r):
                    ranges.remove(i)
                else:
                    to_insert = False
            # l contains i
            if l[0]<i[0] and l[1]>i[1]:
                to_insert = False
        if to_insert:
            ranges.append(l)
    return ranges

- Herrington Darkholme

---

O(n^2)时间复杂度。较慢。 - richselian

也许这个问题可以通过堆来解决。由于所有的列表都不重叠，它们可以用二叉堆表示，其中start和end作为值。这应该将时间复杂度优化为log(n)。 - Herrington Darkholme

Answer 4

通常情况下，如果两个区间重叠，则：

min([upperBoundOfA, upperBoundOfB]) >= max([lowerBoundOfA, lowerBoundOfB])

如果是这种情况，这些间隔的并集为：

(min([lowerBoundOfA, lowerBoundOfB]), max([upperBoundOfA, upperBoundOfB])

同样地，这些区间的交集将是：

(min([upperBoundOfA, upperBoundOfB]), max([lowerBoundOfA, lowerBoundOfB]))

- Joel Cornett

---

我认为在这种特殊情况下找到交集或并集并没有帮助，但这是一些非常有用的通用建议，我会记在心里。谢谢！ - user2338068

Answer 5

1. 按长度升序排序所有项目。

2. 将它们添加到线段树中，并忽略重叠的项目。

- richselian

---

这样做是最优化的方式吗？我会研究一下 - 谢谢！ - user2338068