Wie werden Schnittpunkte von Zeitbereichen berechnet?

Question

Ich habe eine Textdatei bekam, dass alle Zeilen wie:

8:30 8:50 1

..........

20:30 20:35 151

Jede Zeile ist eine neue Benutzerverbindung mit der Zeit in In-Net.

Ziel ist es, Zeiträume zu finden, in denen die Menge das Maximum erreicht. Also, vielleicht kennt jemand Algorithmus, der mir bei dieser Aufgabe helfen kann (mehrere Kreuzungen)? Finden Sie diese Aufgabe nicht-trivial für mich (weil ich neu in der Programmierung bin), ich habe einige Ideen, aber ich finde sie schrecklich, deshalb sollte ich vielleicht mit mathematischen Algorithmen anfangen, den besten Weg zu machen, um mein Ziel zu erreichen.

Answer 1

Für Anfang haben wir einige Annahmen getroffen werden zuerst enthalten.

1. Angenommen, Sie suchen nach dem kürzesten Zeitraum mit maximalen Verbindungen.
2. Angenommen, jede Linie repräsentiert eine Verbindung. Es ist nicht klar aus unserer Frage, was sind die ganzen Zahlen nach Beginn und Ende mal auf jeder Zeile. Also ignoriere ich es.
3. Die Zeilen werden in der Reihenfolge der Startzeit der zunehmenden Periode angegeben.
4. Wir können ein beliebiges lokales Maximum als Antwort wählen, falls wir mehrere Perioden mit der gleichen Anzahl gleichzeitiger Verbindungen haben.

Die erste Stufe der Lösung ist Parsing. Bei einer Folge von Zeilen erhalten wir die Reihenfolge der Paare System.DateTime - ein Paar für jede Periode in der Reihenfolge.

static Tuple<DateTime, DateTime> Parse(string line) 
{ 
    var a = line.Split() 
      .Take(2)  // take the start and end times only 
      .Select(p => 
        DateTime.ParseExact(p, "H:m", 
             CultureInfo.InvariantCulture)) 
      .ToArray(); 
    return Tuple.Create(a[0], a[1]); 
} 

Die nächste Stufe ist der Algorithmus selbst. Es besteht aus zwei Teilen. Zuerst finden wir lokale Maxima als Triple von Startzeit, Endzeit und Verbindungsanzahl. Zweitens: Wir wählen das absolute Maximum aus der Menge durch den ersten Teil hergestellt:

File.ReadLines(FILE_PATH).Select(Parse).GetLocalMaximums().Max(x=>x.Item3) 

File.ReadLines(FILE_PATH).Select(Parse).GetLocalMaximums() 
    .Aggregate((x, y) => x.Item3 > y.Item3 ? x : y)) 

File.ReadLines(FILE_PATH).Select(Parse).GetLocalMaximums() 
    .Aggregate((x, y) => x.Item3 >= y.Item3 ? x : y)) 

Der anspruchsvollste Teil Erkennung eines lokalen Maximums ist.

1. Nehmen Sie die erste Periode A und schreiben Sie ihre Endzeit auf. Notiere dann seine Startzeit als letzte bekannte Startzeit. Hinweis: Es gibt ein Ende Zeit geschrieben und es gibt eine aktive Verbindung.
2. Nehmen Sie die nächste Periode B und schreiben Sie ihre Endzeit. Vergleichen Sie den Start Zeit von B mit dem Minimum der Endzeiten geschrieben.
3. Wenn keine geschriebene Endzeit kleiner als die Startzeit von B ist, erhöht sich die Anzahl der Verbindungen zu dieser Zeit um .Verwerfen Sie also den vorherigen Wert für die letzte bekannte Startzeit und ersetzen Sie ihn durch B's Start Zeit. Fahren Sie dann mit der nächsten Periode fort. Beachten Sie noch einmal, es gibt eine weitere Verbindungen zu dieser Zeit und wir haben noch eine Endzeit. So ist die Nummer der aktiven Verbindungen immer gleich der Anzahl der aufgeschriebenen Ende mal.
4. Wenn es einen Wert in der Liste der Endzeit kleiner als B's Ende gibt, haben wir eine Verringerung der Anzahl der Verbindungen und das bedeutet, wir haben gerade ein lokalen Maximum (hier ist die Mathematik). Wir müssen es melden: erhalte das Triple (die letzte bekannte Startzeit, das Minimum der geschriebenen Endzeiten, die Anzahl der Endzeiten minus eins geschrieben). Wir sollten die Endzeit für B , die wir bereits geschrieben hatten, nicht zählen. Dann verwerfen Sie alle Endzeiten weniger als als Bs Startzeit, ersetzen Sie die letzte bekannte Startzeit und fahren Sie mit auf die nächste Periode.
5. Wenn die minimale Endzeit gleich dem Start von B ist, bedeutet das, dass wir eine Verbindung verloren haben und gleichzeitig eine andere Verbindung haben. Das bedeutet Wir müssen die Endzeit verwerfen und mit der nächsten Periode fortfahren.
6. Wiederholen Sie Schritt 2 für alle Zeiträume, die wir haben.

Der Quellcode für die lokale Maximum Erkennung

static IEnumerable<Tuple<DateTime, DateTime, int>> 
     GetLocalMaximums(this IEnumerable<Tuple<DateTime, DateTime>> ranges) 
{ 
    DateTime lastStart = DateTime.MinValue; 
    var queue = new List<DateTime>(); 
    foreach (var r in ranges) 
    { 
     queue.Add(r.Item2); 
     var t = queue.Min(); 
     if (t < r.Item1) 
     { 
      yield return Tuple.Create(lastStart, t, queue.Count-1); 
      do 
      { 
       queue.Remove(t); 
       t = queue.Min(); 
      } while (t < r.Item1); 
     } 

     if (t == r.Item1) queue.Remove(t); 
     else lastStart = r.Item1; 
    } 

    // yield the last local maximum 
    if (queue.Count > 0) 
     yield return Tuple.Create(lastStart, queue.Min(), queue.Count); 
} 

Während List(T) Verwendung war nicht die beste Entscheidung, es ist leicht zu verstehen. Verwenden Sie eine sortierte Version der Liste für eine bessere Leistung. Durch das Ersetzen von Tupeln durch Strukturen werden viele Speicherzuweisungsoperationen überflüssig.

Answer 2

Sie könnten tun:

string[] lines=System.IO.File.ReadAllLines(filePath) 
var connections = lines 
    .Select(d => d.Split(' ')) 
    .Select(d => new 
    { 
     From = DateTime.Parse(d[0]), 
     To = DateTime.Parse(d[1]), 
     Connections = int.Parse(d[2]) 
    }) 
    .OrderByDescending(d=>d.Connections).ToList(); 

Verbindungen die sortierte Liste mit den Top-Ergebnisse