Merge-Bereiche in Abständen

Gegeben sei eine Menge von Intervallen: {1-4, 6-7, 10-12} hinzufügen eines neuen Intervalls: (9,11), so dass die endgültige Lösung ist 'zusammengefasst': Output: {1-4, 6-7, 9-12}. Die Fusion kann passieren, auf beiden Seiten (low-als auch high range).

Sah ich diese Frage beantwortet wurde, an mehreren Orten, jemand hat sogar vorgeschlagen, Intervall-Bäume, aber nicht erklären, wie genau Sie es verwenden würden. Die einzige Lösung die ich kenne ist, ordnen Sie die Intervalle in aufsteigender Reihenfolge Ihrer start-und iteriert Sie und versuchen, mischen Sie Sie entsprechend.

Wenn mir jemand helfen kann zu verstehen, wie können wir verwenden, Intervall-Bäume in diesem Anwendungsfall wird es großartig sein!

[I wurden folgende Intervall-Bäume in CLRS-Buch, aber sprechen Sie nicht über Fusion, alles, was Sie sprechen, ist, einfügen und suchen.]

Diese Antwort: stackoverflow.com/a/6462731/1296661 erwähnt Algorithmus für die Zusammenführung der Intervall-Bäume

InformationsquelleAutor Darth.Vader | 2013-01-27

6

(Ich gehe davon aus, dass dies bedeutet, dass Intervalle können nie überlappen, da Sie sonst würde zusammengeführt werden.)

Einen Weg, dies zu tun wäre, um zu speichern eine ausgewogene binären Suchbaum einen Knoten pro Endpunkt eines Bereichs sein. Jeder Knoten würde dann so markiert werden, dass entweder eine "offene" Knoten markiert den Beginn eines Intervalls oder ein "schließen" - Knoten markiert das Ende eines Intervalls.

Beim einfügen einer neuen Reihe, einer der beiden Fälle auftreten, in Bezug auf den Startpunkt der Strecke:
1. Es schon im a-Bereich, was bedeutet, dass Sie erweitern das bereits bestehende Angebot als Teil der insertion.
2. Es nicht in eine Reihe, so werden Sie in die Schaffung einer neuen "open" - Knoten.
Um zu bestimmen, welche, wenn Sie in sind, können Sie eine Vorgänger-Suche in der Baumstruktur für den Bereich start-Punkt. Wenn Sie NULL-oder nahe-Knoten, müssen Sie eine neue open-Knoten, der für den start-Punkt der Reihe. Wenn Sie einen Knoten öffnen, Sie halten gerade die Verlängerung des Intervalls.

Gibt, werden Sie brauchen, um zu bestimmen, wie weit das Spektrum reicht. Um dies zu tun, ständig die Berechnung der Nachfolger des ersten Knotens eingefügt, bis eines der folgenden Ereignisse Eintritt:
1. Haben Sie schaute auf alle Knoten im Baum. In diesem Fall müssen Sie eine enge Knoten markiert das Ende dieses Intervalls.
2. Sehen Sie eine enge Knoten nach dem Ende der Reihe. In diesem Fall sind Sie in der Mitte eines vorhandenen Bereichs, wenn der neue Bereich endet, so dass Sie nicht brauchen nichts mehr zu machen. Sie sind fertig.
3. Sehen Sie ein schließen oder öffnen Sie den Knoten vor dem Ende der Reihe. In diesem Fall müssen Sie entfernen dieses Knotens aus dem Baum, da der alte Bereich wird subsumiert, durch die neue ersetzt.
4. Sehen Sie eine offene Knoten nach dem Ende der Reihe. In diesem Fall legen Sie eine neue enge Knoten in den Baum, da müssen Sie beenden das aktuelle Angebot zu sehen, bevor der start dieser neuen.
Umgesetzt naiv, die Laufzeit dieses Algorithmus ist O(log n + k log n), wobei n die Anzahl der Intervalle und k ist die Anzahl der Intervalle entfernt, die während dieses Prozesses (da haben Sie zu tun, n löscht). Sie können jedoch die Geschwindigkeit bis zu O(log n) durch Verwendung der folgenden trick. Da der Löschvorgang löscht immer die Knoten in einer Reihenfolge, die Sie verwenden können, eine Nachfolger-Suche für den Endpunkt zu bestimmen, die das Ende des Bereichs zu entfernen. Dann können Sie splice den Teilbereich zu entfernen aus dem Baum durch zwei tree-split-Operationen und ein Baum join-operation. Auf einer geeignet ausgewogenen Baum (rot-schwarz oder einen Winkelbereich, beispielsweise) kann dies in O(log n) Zeit insgesamt, das geht viel schneller, wenn viele Bereiche gehen, subsumiert.

Hoffe, das hilft!
- Für den start-Punkt der Einfügung Fall: zuerst prüfen, ob ein Knoten mit dem gleichen Wert vor der Suche nach einem Vorgänger. Wenn dieser existiert und ist ein "öffnen" - Knoten ist, sind Sie fertig (nichts für den Startpunkt), wenn es eine "schließen" - Knoten, den Sie löschen müssen, um diesen Knoten (das Intervall wird verlängert).
InformationsquelleAutor templatetypedef

public class MergeIntervals {

public static class Interval {

    public double start;
    public double end;

    public Interval(double start, double end){
        this.start = start;
        this.end = end;
    }
}

public static List<Interval> mergeInteval(List<Interval> nonOverlapInt, Interval another){

    List<Interval> merge = new ArrayList<>();

    for (Interval current : nonOverlapInt){

        if(current.end < another.start || another.end < current.start){
            merge.add(current);
        }
        else{

            another.start = current.start < another.start ? current.start : another.start ;
            another.end = current.end < another.end ? another.end : current.end;                
        }           
    }
    merge.add(another);
    return merge;   
}

InformationsquelleAutor Gökhan Akduğan

0

Check this out. Es kann Ihnen helfen:- http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/index.html

Die Bibliothek bietet die folgenden Funktionalitäten:

1) interval_set

2) separate_interval_set

3) split_interval_set
- Danke, aber ich bin mehr daran interessiert, den Algorithmus anstatt einer handelsüblichen Bibliothek/API.
- Ein einfacher Algorithmus könnte sein, dass Sie zuerst Sortieren Sie die Bereiche, indem Sie die Ausgangswerte und dann Durchlaufen Sie die Bereiche von Anfang bis Ende, und wenn Sie finden ein Sortiment, das überschneidet sich mit dem nächsten ein, mischen Sie Sie
- Ja, ich weiß schon, über, die. Zitat aus meiner Frage: "Die einzige Lösung, die ich kenne, ist, Verschiebe die Intervalle in ascendening der Reihenfolge Ihrer start-und iteriert Sie und versuchen, mischen Sie Sie entsprechend.". Ich bin auf der Suche nach einer optimalen Lösung (möglicherweise mit Intervall-Bäume????)
InformationsquelleAutor Rahul Tripathi

public class Interval
{
    public Interval(int start, int end) { this.start = start; this.end = end; }
    public int start;
    public int end;
}

void AddInterval(List<Interval> list, Interval interval)
{
    int lo = 0;
    int hi = 0;
    for (lo = 0; lo < list.Count; lo++)
    {
        if (interval.start < list[lo].start)
        {
            list.Insert(lo, interval);
            hi++;
            break;
        }
        if (interval.start >= list[lo].start && interval.start <= list[lo].end)
        {
            break;
        }
    }
    if (lo == list.Count)
    {
        list.Add(interval);
        return;
    }

    for (hi = hi + lo; hi < list.Count; hi++)
    {
        if (interval.end < list[hi].start)
        {
            hi--;
            break;
        }
        if (interval.end >= list[hi].start && interval.end <= list[hi].end)
        {
            break;
        }
    }
    if (hi == list.Count)
    {
        hi = list.Count - 1;
    }

    list[lo].start = Math.Min(interval.start, list[lo].start);
    list[lo].end = Math.Max(interval.end, list[hi].end);

    if (hi - lo > 0)
    {
        list.RemoveRange(lo + 1, hi - lo);
    }
}

InformationsquelleAutor user7431997

-1

Das geschieht einfach durch addieren des Intervalls in Frage, um das Ende des Intervalls gesetzt, dann ein merge auf allen teh Elemente des Intervalls festgelegt.

Den merge-Vorgang ist detailliert hier: http://www.geeksforgeeks.org/merging-intervals/

Wenn Sie nicht in der Stimmung für C++ - code, hier ist die gleichen Dinge in python:

def mergeIntervals(self, intervalSet):
    # interval set is an array.
    # each interval is a dict w/keys: startTime, endTime.  
    # algorithm from: http://www.geeksforgeeks.org/merging-intervals/
    import copy
    intArray = copy.copy(intervalSet)
    if len(intArray) <= 1:
        return intArray
    intArray.sort(key=lambda x: x.get('startTime'))
    print "sorted array: %s" % (intArray)
    myStack = []  #append and pop.
    myStack.append(intArray[0])
    for i in range(1, len(intArray)):
        top = myStack[0]
        # if current interval NOT overlapping with stack top, push it on.
        if   (top['endTime'] < intArray[i]['startTime']):
            myStack.append(intArray[i])
        # otherwise, if end of current is more, update top's endTime
        elif (top['endTime'] < intArray[i]['endTime']):
            top['endTime'] = intArray[i]['endTime']
            myStack.pop()
            myStack.append(top)

    print "merged array: %s" % (myStack)
    return myStack

Vergessen Sie nicht, Ihre nosetests zu überprüfen, ob Sie tatsächlich die richtige Arbeit:

class TestMyStuff(unittest.TestCase):

    def test_mergeIntervals(self):
        t = [ { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 11, 'endTime' : 15  }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46  } ]
        mgs = MyClassWithMergeIntervalsMethod()
        res = mgs.mergeIntervals(t)
        assert res == [ { 'startTime' : 11, 'endTime' : 15  }, { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 44, 'endTime' : 46  }, { 'startTime' : 72, 'endTime' : 76 } ]

        t = [ { 'startTime' : 33, 'endTime' : 36 }, { 'startTime' : 11, 'endTime' : 35  }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46  } ]
        mgs = MyClassWithMergeIntervalsMethod()
        res = mgs.mergeIntervals(t)
        assert res == [{'endTime': 36, 'startTime': 11}, {'endTime': 46, 'startTime': 44}, {'endTime': 76, 'startTime': 72}]

InformationsquelleAutor Kevin J. Rice

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.