Funtional Weise leeren Abständen in einer Liste von Tupeln mit Start- und Endzeiten

Question

Sagen wir, ich habe eine Liste von Tupeln mit Start- und Endzeiten zu finden:

List((1,10), (2,11), (3,11), (13,14)) 

Die einzige Entspannung dh Startzeiten sind aufsteigend

ich erwarte, dass die folgende Ausgabe:

List((0,1), (11,13)) 

Das Verfahren Umsetzung ist recht einfach, aber ich würde keine Ahnung, diese (idiomatisch) funktionsfähig zu machen.

Eine Scala-for-Yield-Schleife scheint eine schlechte Anpassung zu sein, da das Ergebnis die gleiche Größe wie die Eingabe hätte. Während eine Verkleinerung/Falte mich beschränken würde, nur ein Tupel als die Antwort zu haben.

Answer 1

Betrachten Sie die folgende Lösung:

list 
    .foldLeft((List[(Int,Int)](), 0)) { 
    case ((res, se), (s, e)) => 
     if(s>se) ((se, s)::res,e) 
     else (res, e) 
    } 
    ._1 
    .reverse 

Erklärung. Wir akkumulieren Wertepaare: Liste der leeren Intervalle (die anfangs leer ist, List (Int, Int)) und Ende des letzten Intervalls (anfangs 0). Nehmen Sie für jeden Schritt das aktuelle Intervall (s, e) und vergleichen Sie es mit dem Ende des letzten Intervalls. Wenn Beginn des aktuellen Intervalls von mehr als Ende des letzten dann eine Lücke gibt und wir nehmen es führen: (se, s)::res

Answer 2

Sie eine Kombination aus scanLeft

list.scanLeft((0,0,0))((l,r) => 
    if(r._1 > l._3) {(l._2, r._1, r._2)} 
    else {(l._1,r._2, r._2)}) 
filter(x => x._2 != x._3) 
map(x => (x._1, x._2)) 

Während des Scans verwenden kann ein Filter und eine Karte, die wir Betrachten Sie das rechte Element des Scan-Paars, dh einen Job, um zu sehen, ob es größer als die Endzeit ist (eingeleitet mit dem Tripel (0,0,0)). Wenn ja, geben wir ein Triplett enthält, um,

1. Der Beginn der Lücke
2. Das Ende der Lücke
3. Die Stoppzeit des Jobs, der die Lücke beendet.

Wenn die rechte Hand, dh Aufgabe der, Startzeit nicht größer ist als die linke Hand der Endzeit ist, gibt es keine leere Lücke und wir schaffen ein Triplett, die die aktuellen Job-Streifen (durch einen Mangel an einem vergrößert bessere Bezeichnung), durch

1. Kopie der Job-Streifen Startzeit
2. der letzte Job Endzeit
3. gleiche wie 2.

kopieren können wir jetzt identifizieren Lücken, indem Sie sehen, dass das zweite und dritte Element der Drillinge unterschiedlich sind (verifizieren Sie, dass dies eine iff-Beziehung ist). Wir filtern jetzt nach dieser Tatsache. Schließlich ordnen wir zu, damit wir das passende Ausgabeformular erhalten.