How to reduce a collection of ranges to a minimal set of ranges

Question

I'm trying to remove overlapping values from a collection of ranges.

The ranges are represented by a string like this:

499-505 100-115 80-119 113-140 500-550

I want the above to be reduced to two ranges: 80-140 499-550. That covers all the values without overlap.

Currently I have the following code.

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

I split the array by - and store the range limits in ar and br. I iterate over these limits pairwise and if the i is at least as great as the j, I want to delete the element. But the program doesn't work. I expect it to produce this result: 80-125 500-550 200-250 180-185

You're adding `jnc` (0) to itself. Do `jnc += 1` instead--and for `inc`. — cwahls, Dec 24 '15 at 06:05

score 6 · Answer 1 · answered Dec 24 '15 at 06:44

For a quick and short solution,

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']

For the given set in your program, output is ['80-125', '180-185', '200-250', '500-550'] Main Possible drawback of this solution: This may not be scalable!

Michael Laszlo · Accepted Answer · 2015-12-24T07:10:31.450

Let me offer another solution that doesn't take time linearly proportional to the sum of the range sizes. Its running time is linearly proportional to the number of ranges.

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 ]

This function works by sorting the ranges, then looking at them in order and merging consecutive ranges that intersect.

Examples:

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

How to reduce a collection of ranges to a minimal set of ranges

2 Answers2