0

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?

rrryok
  • 55
  • 4
  • Are the endpoints of the segments inclusive or exclusive? (e.g. if I have `[[8, 12], [12, 14]]`, what is the desired output?) – BrokenBenchmark Jan 27 '22 at 17:49
  • @BrokenBenchmark I don't have those items but output will be [8,14] – rrryok Jan 27 '22 at 17:55
  • 1
    Does this answer your question? [Merging Overlapping Intervals in Python](https://stackoverflow.com/questions/49071081/merging-overlapping-intervals-in-python) – Tomerikoo Jan 27 '22 at 17:56
  • Does this answer your question? [Merging Overlapping Intervals](https://stackoverflow.com/q/43600878/6045800) – Tomerikoo Jan 27 '22 at 17:58
  • Does this answer your question? [Combine overlapping ranges of numbers](https://stackoverflow.com/q/58535825/6045800) – Tomerikoo Jan 27 '22 at 18:01

1 Answers1

0

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).

BrokenBenchmark
  • 18,126
  • 7
  • 21
  • 33
  • 1
    Please consider removing this answer as this question is a duplicate. If your answer doesn't exist in the [dupe target](https://stackoverflow.com/q/43600878/6045800), please post it there – Tomerikoo Jan 27 '22 at 18:00