Suchen Sie nach zwei getrennten Intervallsätzen die Schnittpunkte

1774
user151542
def getIntersection(set_item1, set_item2):
    (l11, l12) = set_item1
    (l21, l22) = set_item2
    if (l11 > l21 and l11 < l22) or (l12 > l21 and l12 < l22) or (l21 > l11 and l21 < l12) or (l22 > l11 and l22 < l12):
        if l11 > l21:
            start = l11
        else: start = l21

        if l12 > l22:
            end = l22
        else:
            end = l12
        return (start ,end)
    return None

def returnInersection(set1, set2):
    for l1 in set1:
        for l2 in set2:
            ret = getIntersection(l1, l2)
            if ret:
                print ret

Ich denke, über eins funktioniert gut, aber es läuft in O (n 2 ). Gibt es eine bessere Lösung?

Beispieleingabe kann set1=[(1, 6), (10, 15), (20, 30)]und sein set2=[(2, 5), (7, 13)].

Antworten
3
Dies ist eine wirklich gute erste Frage. Du solltest dich gut fühlen. Oscar Smith vor 2 Jahren 0
Werden die Eingabeintervalle garantiert nicht innerhalb eines Satzes überlappen? Werden die Sätze garantiert in aufsteigender Reihenfolge der Untergrenze gegeben? Überschneiden sich oder nicht (1, 2) und (2, 3)? (Was wären * zwei nicht disjunkte Mengen *?) greybeard vor 2 Jahren 1

2 Antworten auf die Frage

1
Oscar Smith

Die wirklich niedrig hängende Frucht verbessert sich. getIntersectionAnstelle einer speziellen Hülle kann man einfach sagen, dass der Schnittpunkt der Abstand zwischen dem Maximum der Minuten und dem Minimum der Maxes ist (wenn das Ende größer als der Anfang ist). Wenn wir gerade dabei sind, könnten wir einige der Namensprobleme aufräumen.

def getIntersection(interval_1, interval_2):
    start = max(interval_1[0], interval_2[0])
    end = min(interval_1[1], interval_2[1])
    if start < end:
        return (start, end)
    return None

Dies ist einfacher, sauberer und schneller zu starten.

Das nächste, was wir tun können, um von hier aus etwas zu beschleunigen, ist, zwei Tatsachen zu beachten, die auftreten, weil die Intervalle unzusammenhängend sind.

  1. Wenn intervals1[i]schneidet mit intervals2[j], intervals1[i+1]schneidet nicht mit intervals2[j].
  2. Wenn sie intervals1[i]sich nicht mit schneidet intervals2[j], schneidet sie nicht mit intervals2[j+1].

Ihr ursprünglicher returnInersectionCode liegt darin, O(n^2)dass er das Kreuzprodukt der beiden Listen durchsucht. Jede der oben genannten Regeln begrenzt fast die Hälfte des Speicherplatzes. Wenn Sie beide verwenden, prüfen Sie nur nach O(n)Schnittpunkten (im Wesentlichen die Diagonale). Dieser Code tut dies.

def returnInersection(intervals1, intervals2):
    start = 0
    for interval1 in intervals1:
        found_yet = False
        for j in range(start, len(intervals2)):
            intersection = getIntersection(interval1, intervals2[j])
            if intersection:
                print(intersection)
                found_yet = True
                start += 1
            elif found_yet:
                break

Ich bin sicher, dass es immer noch Wege gibt, dies zu beschleunigen, aber es ist zumindest algorithmisch optimal.

Ich würde es vorziehen, die Kreuzung anstelle von "Druck" zu "nachgeben". Auf diese Weise kann der Benutzer dieses Algorithmus mit dem Ergebnis etwas anfangen. Sie könnten auch 'für Intervall2 in Intervallen2 [Start:]: `anstelle von` für j im Bereich (Start, Länge (Intervalle2)): `tun. Wenn 'Intervall1 [0] `>' Intervall2 [1]` ohne Schnittpunkt ist, können Sie auch 'Start' erhöhen Maarten Fabré vor 2 Jahren 0
1
Maarten Fabré

Anleihen für Oscar Smiths Lösung

Wenn intervalsXSie bestellt werden, können Sie einfach Folgendes verwenden:

def return_intersections(intervals1, intervals2):
    iter1 = iter(intervals1)
    iter2 = iter(intervals2)

    interval1 = next(iter1)
    interval2 = next(iter2)

    while True:
        intersection = getIntersection(interval1, interval2)
        if intersection:
            yield intersection
            try:
                if intersection[1] == interval1[1]:
                    interval1 = next(iter1)
                else:
                    interval2 = next(iter2)
            except StopIteration:
                return

        try:
            while interval1[0] > interval2[1]:
                interval2 = next(iter2)
            while interval2[0] > interval1[1]:
                interval1 = next(iter1)
        except StopIteration:
            return
list(return_intersections(set1, set2))
[(2, 5), (10, 13)]

In Python vor 3.5 war die gesamte try-exceptBoilerplate nicht notwendig, aber pep-476 änderte dies.

Der Vorteil davon ist, dass es für jeden Strom von geordneten Intervallen funktioniert. So intervalsXkann ein Generator, Liste, Tupel, ... sein