如何将范围集合减少到最小范围集

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

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 http://stackoverflow.com/questions/2154249
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'] 主要此解决方案的可能缺点:这可能不可扩展!