finding an union of intersecting elements in a list of segments

Question

I have a segments list:

lst = [[1,5],[2,7],[8,13],[12,15],[3,4]]

First and second elements intersect, so i combine them and so on.I need to get this list:

lst1 = [[1,7],[8,15]]

I have problem when 3 or more segments intersect with ourselves. I tried to fill the missing numbers, and find union using sets

unions = []
for i in range(len(lst)):
    for j in range(i,len(lst)):
        if len(list(set(lst[i]) & set(lst[j]))) != 0:
            unions.append(list(set(lst[i]) | set(lst[j])))

but I think it is wrong way.How can I do this without using any libraries?

Answer 1

You can do the following:

• sort the array by start points of the segments.
• make one pass through the array. For each segment, if the start point is strictly greater than the previous segment's end point, then that segment marks the beginning of a new segment in the merged output. Otherwise, merge it with the previous segment.

Here is the code implementing this algorithm:

import math

def get_union(lst):
    if len(lst) == 0:
        return []

    sorted_list = sorted(lst)
    merged_intervals = []
    [start, end] = lst[0]

    for index, interval in enumerate(sorted_list):
        [current_interval_start, current_interval_end] = interval
        if end < current_interval_start:
            merged_intervals.append([start, end])
            start = current_interval_start
            end = current_interval_end
        else:
            end = current_interval_end

    merged_intervals.append([start, end])

    return merged_intervals

This runs in O(n log n) time, because sorting the array takes O(n log n) time, and the merging process takes linear time. This is faster than using two nested for loops as done in your approach (which takes quadratic time).