Algorithm: Merging Matching Segments

Question

I have an ADT (not sorted): List<Segment>

 //direction is from 0 to 2pi class Segment { int start; int end; } 

They represent, for example, such a situation:

How to make a merge phase (green arrow in the example)? Obviously, I need to iterate over the list and each segment in comparison with all other segments, and for each pair, if possible, make a simple merge (this is easy). But then in the second iteration, I need to somehow return to the top of the list and start all over again, etc. So I'm struggling to find a way to bring this algorithm closer together.

EDIT: segments can be circular - from 1.75pi to 0.5pi, etc.

Answer 1

Sort segments by start time.

Create a stack that will store the combined intervals.

Add the first element of the sorted array to the stack, then for each element in the array compare it with the element at the top of the stack

If the start time is longer than the end time of the item at the top of the stack, add an interval to the stack.

If the start time is less than the end time of the element at the top of the stack, update the end time of the element at the top of the stack to match the end time of the new element.

When the entire array is processed, the resulting stack must contain the combined intervals.

Java implementation:

 /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public List<Interval> merge(List<Interval> intervals) { Deque<Interval> stack = new ArrayDeque<Interval>(); Collections.sort(intervals, new Comparator<Interval>() { public int compare(Interval p1, Interval p2) { return Integer.compare(p1.start, p2.start); } } ); if (intervals.size() < 1) { return intervals; } stack.push(intervals.get(0)); for (int j = 1; j < intervals.size(); j++) { Interval i = intervals.get(j); Interval top = stack.peek(); if (top.end < i. start) { stack.push(i); } else if (top.end < i.end) { top.end = i.end; } } return new ArrayList<Interval>(stack); } } 

Answer 2

Sort segments by starting point.

Then for each segment, if its start point is between the start and end points of the previous segment, and its end point is greater than the end point of the previous segment, set the end point of the previous segment to this end point of the segment and delete / ignore the current segment.

If the current segment is fully included in the previous segment, simply delete / ignore it.

This is O(n log n) due to sorting, and you do not need to compare each segment with all other segments.

Be careful how you do deletion or ignore. This should be operation O(1) . For example, save a variable that always stores the previous non-deleted segment and possibly some flag for the deleted segments so you know which ones to collect at the end. .remove() collection operations can be O(n) , and you want to avoid this.

Answer 3

Put all the endpoints in one array and assign them polarity ( + then - ). Then sort the list.

When you go through the list, increasing the value, it is enough to update the counter of overlapping segments.

 0+ 0.75- 0.5+ 1- 1.25+ 2- 

then sorted,

 0+ 0.5+ 0.75- 1- 1.25+ 2- 

gives counts (initialized to 0 )

 1 2 1 0 1 0 

therefore, the interval boundaries (at transitions 0 to >0 or >0 to 0 )

 0 1 1.25 2 

---

This can also be done cleanly in place , without additional flags .

You sort the start and end values ​​separately, in place (do not move the Segments as a whole); thus, the polarities remain implicit.

Then cross the list as a merge of two sorted lists (using two independent indexes) and save the overlap counter. You can rewrite borders in place, since the result of the merge has no more intervals.

Beginning with

 [0 0.75][0.5 1][1.25 2] 

both lists are randomly sorted.

 0 0.5 1.25 (+) 0.75 1 2 (-) 

Go to the merge, which will select the items in order

 + + - - + - 

and the end result is obtained by shifting the values

 [0 1][1.25 2][xx] 

---

In the case of ties at the borders, it is better to handle + and - in this order so that you do not select two equal borders.

Answer 4

I will add a roundness approach to the other answers, i.e. what should you do if you have segments alternating over 2pi.

There are two ways to handle this. One of them is to simply split each such segment into two: one goes from place to 2pi, and the other from zero to place. After that, solve the problem as if it weren't circular, and then if you have a segment starting at zero and a segment ending at 2pi, then just merge them.

The second approach is specifically for Yves Daust's answer. There you only need to know how many segments the zero point covers (you can easily calculate this); after that, you initialize the “account” not with zero, but with so many coverage segments.