wie man Intervalle effizient überschneidet

Question

Ich benötige Ihre Hilfe, ich habe ein Problem (siehe Bild), ich habe sagen wir zwei Arrays und jeder dieser Array enthält Intervalle mit unterschiedlicher Länge und realen Werten und ich muss herausfinden, wie ich bin gegangen überlappen diese Intervalle effizient.

Ich bin offen für Ideen, oder Papiertheorie oder konkrete Algorithmen, die mich einen Ausweg finden lassen! Ich denke darüber nach, dies irgendwie in Wellen zu transformieren und diese zu überlagern.

Das ist sehr wichtig, denn es geht um meine Diplomarbeit.

als Beispiel, hier in Zahlen, um es besser zu erklären:

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

Das Ergebnis ist dann ein einziges Array, das die neuen Intervalle enthält.

Sekundenintervall (Array eins und zwei) überschneiden sich.

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

Ich denke über "Intervall Baum", aber es ist nicht ausreichend, wie ich bin gegangen verschmelzen sie.

Vielen Dank im Voraus!

Answer 1

1) Legen Sie alle Ihre Intervalle in einem Array ab.

2) Sortiere das Feld nach der unteren Grenze jedes Intervalls.

3) Schleife durch die Intervalle von der niedrigsten Untergrenze bis zur höchsten Obergrenze:

a) Wenn das Intervall nach diesem Intervall beginnt, bevor dieses Intervall endet, führe sie zusammen (lösche das zweite Intervall und erweitere dieses Intervall, um seine obere Grenze zu erhalten).

b) Wiederholen Sie den Vorgang, bis das nächste Intervall nach dem Ende dieses Intervalls beginnt.

4) Wiederholen Sie den Vorgang, bis Sie das letzte Intervall erreicht haben.

Answer 2

Hier ist eine Version in Python (Versionen 2 und 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))

Ausgabe:

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

Hinweis: Dies ändert eine Liste von Tupeln an Ort und Stelle. Eine etwas allgemeinere Variante, die mit einer Liste von Iterablen funktioniert, kann durch Ändern der Zeile durchgeführt werden:

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

Wenn Sie wissen, dass Sie eine Liste von veränderbaren Iterablen haben, können Sie alternativ dazu verwenden:

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

Eine alternative Version, die vielleicht etwas leichter zu verstehen ist, lautet:

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

Beachten Sie, dass diese Funktion für eine Liste von Listen gedacht ist.

Answer 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;
}

Dies könnte eine Möglichkeit sein, dies zu tun

Answer 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;
    }   

}

Answer 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