finding unions of line segments on a number line

Question

I have a number-line between 0 to 1000. I have many line segments on the number line. All line segments' x1 is >= 0 and all x2 are < 1000. All x1 and x2 are integers.

I need to find all of the unions of the line segments.

In this image, the line segments are in blue and the unions are in red:

Is there an existing algorithm for this type of problem?

Answer 1

You can use marzullo's algorithm (see Wikipedia for more details). Here is a Python implementation I wrote:

def ip_ranges_grouping(range_lst):
    ##  Based on Marzullo's algorithm
    ##  Input: list of IP ranges
    ##  Returns a new merged list of IP ranges
    table = []
    for rng in range_lst:
        start,end = rng.split('-')
        table.append((ip2int(start),1))
        table.append((ip2int(end),-1))
    table.sort(key=lambda x: x[0])
    for i in range(len(table) - 1):
        if((table[i][0] == table[i+1][0]) and ((table[i][1] == -1) and (table[i+1][1] == 1))):
           table[i],table[i+1] = table[i+1],table[i]

    merged = []
    end = count = 0
    while (end < len(table)):
        start = end
        count += table[end][1]
        while(count > 0): # upon last index, count == 0 and loop terminates
            end += 1
            count += table[end][1]
        merged.append(int2ip(table[start][0]) + '-' + int2ip(table[end][0]))
        end += 1
    return merged