how to overlap intervals efficiently

问题:

I require your help, I have a problem (see picture), I have let say two arrays and each of this array contains intervals with different length and real values and I need to find out how I'm gone overlap this intervals efficiently.

I'm open to ideas, or paper theory or concret algorithms which will let me find a way out! I'm guessing about to transform this somehow in waves and overlap them.

Its very important, its for my thesis.

as an example, here in numbers to explain it better:

1. Array: 1-2, 5-7, 9-12
2. Array: 3-4, 5-6, 13-17

The result will be then one single array containing the new intervals.

second interval (Array one and two) are overlapped.

result Array: 1-2, 3-4, 5-7, 9-12, 13-17

I'm thinking about "interval tree", but its not sufficent how I'm gone merge them.

Thanks in advance!

回答1:

1) Put all of your intervals in one array.

2) Sort that array by the lower bound of each interval.

3) Loop through the intervals from lowest lower bound to highest upper bound:

a) If the interval after this one starts before this one ends, merge them (delete the second one and extend this one to have its upper bound).

b) Repeat until the next interval starts after this one ends.

4) Repeat until you've reached the last interval.

回答2:

Here is a version in python (versions 2 and 3):

def aggregate(data):
    data.sort()
    i = 0
    while i < len(data) - 1:
        while i < len(data) - 1 and data[i][1] >= data[i+1][0]:
            data[i] = (data[i][0], max(data[i][1], data[i+1][1]))
            data.pop(i+1)
        i += 1

if __name__ == '__main__':
    itervals = [(1,2), (5,7), (9,12), (3,4), (5,6), (13,17)]

    formatted = lambda vals: '[{}]'.format(', '.join('({}-{})'.format(
                                                   iterval[0], iterval[1])
                                                   for iterval in sorted(vals)))
    print(formatted(itervals))
    aggregate(itervals)
    print(formatted(itervals))

Output:

[(1-2), (3-4), (5-6), (5-7), (9-12), (13-17)]
[(1-2), (3-4), (5-7), (9-12), (13-17)]

Note: this mutates a list of tuples in-place. A slightly more generic one, that will work with a list of iterables can be done by changing the line:

data[i] = type(data[i])((data[i][0], max(data[i][1], data[i+1][1])))

Alternatively, if you know you have a list of mutable iterables, you could use:

data[i][1] = max(data[i][1], data[i+1][1])

An alternative version, that may be a little easier to follow, is:

def aggregate(data):
    if not data:
        return data

    inputs = sorted(data)
    result = [inputs[0]]

    for next0, next1 in inputs[1:]:
        last0, last1 = result[-1]
        if next0 <= last1:
            result[-1][1] = max(next1, last1)
        else:
            result.append([next0, next1])

    return result

Note that this one is designed for a list of lists.

回答3:

#include <vector>
using namespace std;

struct INTERVAL {
    int a; 
    int b;
};

// v is a sorted vector of intervals (a<=b)
// i is an interval (a<=b) to be merged with v, 
vector<INTERVAL> merge(vector<INTERVAL>& v, INTERVAL& i)
{
    bool fMerged=false; // merged flag
    INTERVAL r=i; // merged interval
    vector<INTERVAL> out; // out vector
    vector<INTERVAL>::size_type k=0; // iterator 

    for(k=0; k<v.size(); ++k) { 
        if (fMerged || v[k].b < r.a) {          
            out.push_back(v[k]); // v[k] comes first
        } 
        else if (r.b<v[k].a) {
            out.push_back(r); // r comes first
            out.push_back(v[k]);
            fMerged=true; // copy rest;
        }
        else { // intervals overlap, merge into r
            r.a=min(v[k].a,r.a); 
            r.b=max(v[k].b,r.b);
        }
    }
    // interval not merged, append to vector
    if (!fMerged) out.push_back(r);
    return out;
}

this could be one way to do it

回答4:

/**
* sort the interval based on the start time
* push the first interval to stack
* compare each interval start time with end time of top of stack
* if interval i th start time is more than  than start and end time of top of stack
* do nothing
* if interval i th  start time is between start and end time of top of stack then
*    update top of stack with ith interval end time
*
*/

import java.util.Stack;
import java.util.Arrays;



public class MergeInterval{

    private static  Stack<Interval> st = new Stack<Interval>();

    class Interval implements Comparable<Interval>{

        public int startTime;
        public int endTime;

        public Interval(int startTime, int endTime){
            this.startTime=startTime;
            this.endTime=endTime;
        }

        @Override
        public int compareTo(Interval i){

            if(startTime <=i.startTime) return 0;
            return 1;
        }

        public boolean canMerge(Interval m){

            if((startTime<=m.startTime) && (endTime>=m.startTime)) return true;
            else return false;
        }

        public String toString(){
            return ("{ "+startTime+" , "+endTime+" } ");
        }
    } 


    private static void findOverlapping(Interval[] setOne){

        //System.out.println(Arrays.toString(setOne));
        Arrays.sort(setOne);
        //System.out.println(Arrays.toString(setOne));
        st.push(setOne[0]);

        for(int i=1;i<setOne.length;i++){

            Interval in = st.peek();

            if(in.canMerge(setOne[i])){
                in.endTime=setOne[i].endTime;
            }else{
                st.push(setOne[i]);
            }

        }

        System.out.println(Arrays.toString(st.toArray()));


    }



    public static void main(String[] args) {

        MergeInterval m = new MergeInterval();
         Interval[] setOne = m.populate();


        findOverlapping(setOne);
    }

    public Interval[]  populate(){

        Interval[] setOne = new Interval[4];
        for(int i=0;i<4;i++){
            setOne[i]=new Interval(1,3);
        }
        setOne[0]=new Interval(1,3);
        setOne[1]=new Interval(2,4);
        setOne[2]=new Interval(5,7);
        setOne[3]=new Interval(6,8);

        return setOne;
    }   

}

回答5:

# Python implementation of http://www.geeksforgeeks.org/merging-intervals/

# Expects a list of (start,end) tuples
def merge_intervals(a):

    # Handle empty list correctly
    if len(a) == 0:
        return []

    # Operate on a copy so the original array is left untouched
    a = list(a)

    # Sort by lower bound
    a.sort()

    # Create stack from first interval
    b = [ a[0] ]

    # Loop through remaining intervals - either merge with top of stack or add
    for idx in xrange(1, len(a)):

        # References to top of stack and current in loop
        previous, current = b[-1], a[idx]

        # New interval if not overlapping
        if previous[1] < current[0]:
            b.append( current )

        # Merge if overlapping (if expands interval)
        elif previous[1] < current[1]:
            b.pop()
            b.append(( previous[0], current[1] ))

    # Return list of merged intervals
    return b

# Test case
if __name__ == '__main__':
    data = [ (1,5), (2,3), (4,6), (7,10), (8,12) ]
    from random import shuffle
    shuffle(data)
    print 'BEFORE', data
    data = merge_intervals(data)
    print 'AFTER', data

回答6:

JAVA Version to accomplish this: Source documenation

public class MergeRange {
    public class Range{
        public int start;
        public int end;
        public Range(int s, int e){
            start = s;
            end = e;
        }

        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }

        @Override
        public boolean equals(Object o) {  
            if (o == this) {
                return true;
            }
            if (!(o instanceof Range)) {
                return false;
            }
            Range c = (Range) o;
            return start == c.start && end == c.end;             
        }
    }

    //compare two range by start, used to sort list of ranges by their starts
    public class RangeComparator implements Comparator<Range> {
        public int compare(Range range1, Range range2) { 
            return Integer.compare(range1.start, range2.start);
        }
    }

    public List<Range> merge(List<Range> ranges){
        if (ranges.size() < 2){
            return ranges;
        }

        ranges.sort(new RangeComparator());
        List<Range> result = new ArrayList<Range>();
        result.add(ranges.get(0));

        for (int i = 1; i < ranges.size(); i++){
            Range lastAdded = result.get(result.size() - 1);
            result.remove(result.size() - 1);
            List<Range> newRanges = merge(lastAdded, ranges.get(i));
            result.addAll(newRanges);           
        }

        return result;

    }
    //merge two ranges where range1.start <= range2.start
    private List<Range> merge(Range range1, Range range2){
        Assert.assertTrue(range1.start <= range2.start);

        if (range1.end < range2.start){
            return Arrays.asList(range1, range2);
        } else{
            Range result = new Range(range1.start, Math.max(range1.end, range2.end));
            return Arrays.asList(result);
        }
    }

}