python - 我应该如何获取包含 [start, end] 范围的列表并将较短的范围“吸收”到重叠的较大范围中？

Question

我目前有一个看起来像这样的列表：

>>> list_in_question = [[0, 4], [0, 3], [0, 4], [3, 4], [6, 7]]

每个列表元素代表一个跨度/范围，第一个元素是开始，第二个是结束。我想采用重叠的元素并将它们组合起来，以便保留最大的范围。没有列表“部分重叠”的情况（例如，[3, 5], [4, 6]）。

我想要的列表是这样的：

>>> list_in_question = [[0, 4], [0, 3], [0, 4], [3, 4], [6, 7]]
>>> list_i_want = [[0, 4], [6, 7]]

我想到的一些方法是制作两个单独的列表来跟踪元素是否有效，但是代码很难阅读并且（我假设）容易出错。它看起来像这样：

valid_lists = []
invalid_lists = []

# Outer loop to go through element lists.
for i, _ in enumerate(list_in_question):
    if list_in_question[i] in valid_lists:
        continue

    # Inner loop to go through subsequent element lists after the i'th one.
    for j in range(i + 1, len(list_in_question)):
        first_range = list_in_question[i]
        second_range = list_in_question[j]

        first_range_expanded = set(range(first_range[0], first_range[1])
        second_range_expanded = set(range(second_range[0], second_range[1])

        if first_range_expanded.issubset(second_range_expanded):
            if second_range not in valid_lists:
                valid_lists.append(second_range)

            invalid_lists.append(first_range)
        elif second_range_expanded.issubset(first_range_expanded):
            if first_range not in valid_lists:
                valid_lists.append(first_range)

            invalid_lists.append(second_range)


for range_list in list_in_question:
    if range_list not in valid_lists and range_list not in invalid_lists:
        valid_lists.append(range_list)

它适用于某些特定情况，但我想知道是否有更好的方法来解决这个问题。谢谢。

标签： python

Answer 1

l = [[0, 4], [0, 3], [0, 4], [3, 4], [6, 7]]

首先，我们可以通过按范围宽度排序来使问题变得更容易（仅通过合并到以前的列表中）（如果需要，我们总是可以稍后恢复顺序）：

l.sort(key=lambda r: r[1] - r[0], reverse=True)

这是有效的，因为如果b被吸收，a我们必须让范围的宽度b更小或等于a（并且当相等时，任何一个都可以被吸收而不改变结果）。

然后（存在更有效的算法，但除非您有大量实例，否则会过度使用），过滤相对简单：

absorbers = []
for r in l:
    absorbed = any(a[0] <= r[0] <= r[1] <= a[1]
                   for a in absorbers)
    if not absorbed:
        absorbers.append(r)