如何将一组范围缩减为最小的范围集合

Question

我正在尝试从一组范围中删除重叠的值。

这些范围由以下字符串表示: 499-505 100-115 80-119 113-140 500-550 我希望将其缩减为两个范围: 80-140 499-550，以覆盖所有值而不重叠。

目前我的代码如下。

cr = "100-115 115-119 113-125 80-114 180-185 500-550 109-120 95-114 200-250".split(" ")
ar = []
br = []

for i in cr:
    (left,right) = i.split("-")
    ar.append(left);
    br.append(right);

inc = 0
for f in br:    

    i = int(f)
    vac = []
    jnc = 0
    for g in ar:
        j = int(g)  
        if(i >= j):
            vac.append(j)
            del br[jnc]
            jnc += jnc 

    print vac 
    inc += inc

我将数组按照-分割，并将范围限制存储在ar和br中。我成对迭代这些限制，如果i至少与j一样大，我想删除该元素。但程序不能正常运行。我希望它能产生以下结果：80-125 500-550 200-250 180-185

- user4284509

---

你正在将 jnc (0) 加上本身。请改为使用 jnc += 1，以及对于 inc 也做同样的修改。 - cwahls

Answer 1

对于一个快速而简短的解决方案，

from operator import itemgetter
from itertools import groupby

cr = "499-505 100-115 80-119 113-140 500-550".split(" ")
fullNumbers = []
for i in cr:
    a = int(i.split("-")[0])
    b = int(i.split("-")[1])
    fullNumbers+=range(a,b+1)

# Remove duplicates and sort it
fullNumbers = sorted(list(set(fullNumbers)))

# Taken From https://dev59.com/2nI95IYBdhLWcg3wyRE0
def convertToRanges(data):
    result = []
    for k, g in groupby(enumerate(data), lambda (i,x):i-x):
        group = map(itemgetter(1), g)
        result.append(str(group[0])+"-"+str(group[-1]))
    return result

print convertToRanges(fullNumbers)
#Output: ['80-140', '499-550']

对于程序中给定的集合，输出结果为['80-125', '180-185', '200-250', '500-550']

该解决方案的主要可能缺陷是：它可能不具有可扩展性！

- Gurupad Hegde

Answer 2

我可以提供另一种解决方案，其所需时间与范围大小的总和成线性比例关系不同。它的运行时间与范围数量成线性比例关系。

def reduce(range_text):
    parts = range_text.split()
    if parts == []:
        return ''
    ranges = [ tuple(map(int, part.split('-'))) for part in parts ]
    ranges.sort()
    new_ranges = []
    left, right = ranges[0]
    for range in ranges[1:]:
        next_left, next_right = range
        if right + 1 < next_left:             # Is the next range to the right?
            new_ranges.append((left, right))  # Close the current range.
            left, right = range               # Start a new range.
        else:
            right = max(right, next_right)  # Extend the current range.
    new_ranges.append((left, right))  # Close the last range.
    return ' '.join([ '-'.join(map(str, range)) for range in new_ranges ]

这个函数的工作原理是先对范围进行排序，然后按顺序查看它们并合并相交的连续范围。

示例：

print(reduce('499-505 100-115 80-119 113-140 500-550'))
# => 80-140 499-550

print(reduce('100-115 115-119 113-125 80-114 180-185 500-550 109-120 95-114 200-250'))
# => 80-125 180-185 200-250 500-550

- Michael Laszlo