Algorithm: Merge overlapping segments

Question

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

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

They representing for example this situation:

How to make the merging phase (green arrow in the example)? Obviously I need to iterate over the list and each segment compare to all other segments, and for each couple if possible to make simple merge (this is easy). But then in the second iteration I need somehow to return to the beginning of the list and start over etc... So I struggle to find how this algorithm will converge.

EDIT: The segments can be circular- From 1.75pi to 0.5pi etc...

Answer 1

Sort the segments by starting time.

Create a stack which will store the merged intervals.

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

If the start time is greater than the end time of the element at the top of the stack, add the interval to the stack.

If the start time is smaller 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 whole array is processed the resulting stack should contain the merged intervals.

Implementation on java:

/**
 * 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 your segments by starting point.

Then, for each segment, if its starting point is between the start and end point of the previous segment and its end point is larger than the previous segment's end point, set the previous segment's end point to this segment's end point and remove / ignore the current segment.

If the current segment is completely included in the previous segment, then just remove / ignore it.

This is O(n log n) because of the sort, and you don't need to compare each segment with all the other segments.

Be careful how you do the removing or ignoring. It should be an O(1) operation. For example, keep a variable that always stores the previous non-removed segment, and maybe some flag for removed segments so you know which ones to collect at the end. .remove() operations on collections can be O(n), and you want to avoid that.

Answer 3

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

As you go traversing the list by increasing value, it suffices to update a 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 the counts (initialized at 0)

1 2 1 0 1 0

hence the interval bounds (on transitions 0 to >0 or >0 to 0)

0 1 1.25 2

---

This can also be done purely in-place, without extra flags.

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

Then traverse the list as a merge of two sorted lists (using two independent indexes), and maintain the overlap counter. You can overwrite the bounds in-place, as the result of the merge doesn't have more intervals.

Starting from

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

both lists are accidentally already sorted.

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

Proceed to the merge, which will select the elements in the order

+ + - - + -

and the final result is obtained by shifting values

[0 1][1.25 2][x x]

---

In case of ties on the bounds, it is better to process the + and the - in an order such that you avoid emitting two equal bounds.

Answer 4

I will add to other answers the approach for the circularity, i.e. what should you do if you have some segments looping over 2pi.

There are two ways to handle this. One is to simple split each such segment into two: one going from wherever to 2pi, the other going from zero to wherever. After this, solve the problem as if it is not circular, and then if you have a segment starting at zero, and a segment ending at 2pi, then just merge them.

A second approach is specifically for Yves Daoust's answer. There all you need is to know how much segments do cover the zero point (you can easily calculate this); after this, you initialize the "counts" not with zero, but with this number of covering segments.