Geek Answers Handbook

Search for line segment joins on a numerical line

I have a number line from 0 to 1000. I have many line segments on a number line. All segments of the line x1 are> = 0 and all x2 are equal to <1000. All x1 and x2 are integers.

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

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

enter image description here

Is there an existing algorithm for this type of problem?

+3
source share
3 answers

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

def ip_ranges_grouping(range_lst): ## Based on Marzullo 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
+2
source

If the segments do not change dynamically, this is a simple problem. Just sort all the segments to the left, then scan the sorted items:

 struct Seg {int L,R;}; int cmp(Seg a, Seg b) {return aL < bL;} int union_segs(int n, Seg *segs, Segs *output) { sort(segs, segs + n, cmp); int right_most = -1; int cnt = 0; for (int i = 0 ; i < n ; i++) { if (segs[i].L > right_most) { right_most = segs[i].R; ++cnt; output[cnt].L = segs[i].L; output[cnt].R = segs[i].R; } if (segs[i].R > right_most) { right_most = segs[i].R; output[cnt].R = segs[i].R; } } return cnt+1; }

The complexity of the time is O (nlogn) (sorting) + O (n) (scanning).

If segments are inserted and deleted dynamically, and you want to request a join at any time, you will need more complex data structures, such as a range tree .

+1
source

Given that the coordinates of your segments are limited to ([0, 1000]) integers, you can use an array of size 1000, initialized to zeros. Then you start your set of segments and set 1 to each cell in the array that covers the segment. Then you only need to run through the array to check for consecutive sequences 1.

 --- ----- --- --- 1111100111111100

The complexity depends on the number of segments, as well as their length.

Here is another method that also works for floating point segments. Sort segments. Then you only need to move the sorted segments and compare the boundaries of each adjacent segment. If they intersect, they are in one union.

+1
source

More articles:


All Articles