Binärer Suchalgorithmus, um Werte zu maximieren

Question

Ich wurde dieses Problem zugewiesen Ich muss lösen:

Es gibt viele geführte Aktivitäten in einem bestimmten Schwimmbad. Daher sind die Benutzungsregeln sehr streng:

Die freien Zeitschlitze sind nur eine Minute lang. Nach der Verwendung eines freien Steckplatzes müssen Sie mindestens x Sekunden warten, bevor Sie einen anderen Steckplatz verwenden. Sie haben die Liste der freien Plätze, und Sie wollen für mindestens m Minuten schwimmen. Was ist das Maximum x, die es erlaubt?

Eingabe

Eingabe besteht aus mehreren Fällen. Jeder Fall beginnt mit der Anzahl der Minuten m und der Anzahl der Steckplätze n, gefolgt von n Tripel H:M:S, die anzeigen, dass es eine Spur gibt, die für eine Minute frei ist, beginnend bei H:M:S. Nehmen Sie an, 2 ≤ m ≤ n ≤ 1000, dass die Stunden zwischen 00:00:00 und 23:59:00 sind, und dass es keine Überlappungen zwischen Zeitschlitzen gibt. Der letzte Eintrag ist mit einem Sonderfall mit m = n = 0 gekennzeichnet.

Ausgabe

Für jeden Fall der maximalen x drucken, die insgesamt Badezeit von m oder mehr Minuten ermöglicht.

Was wäre eine mögliche Implementierung mit binärer Suche über die Variable x, um sie zu maximieren?

Ausgänge des Problems:

input: 
4 8 
00:10:40 00:35:30 01:00:00 01:55:00 02:10:00 03:15:00 12:00:20 23:59:00 
output: x = 11000 

Answer 1

Dies erfordert keine überhaupt suchen. Verwandeln Sie die Liste von freien Zeitfenster, um eine Liste der Wartezeit zwischen den Zeitschlitzen in Sekunden (berücksichtigen Sie eine Minute lang Schwimmen):

waiting_time[] 

for i in [1, length(time_slots)) 
    waiting_time[i - 1] = delta_minutes(time_slots[i - 1], time_slots[i]) * 60 - 60 

Sortieren Sie die Liste von Wartezeiten

sortDesc(waiting_time) 

Da muss man m - 1 mal warten, muss x so gewählt werden, dass mindestens x Wartezeiten mindestens gleich lang sind. Da wir nach dem Maximum x suchen, muss die kleinste Wartezeit genau so lang sein wie x, die das m - 1 ten Element in unserem Array ist.

setzen sie alle zusammen:

minX(input[], m): 
    waiting_time[] 

    for i in [1, length(input)): 
     waiting_time[i - 1] = delta_minutes(time_slots[i - 1], time_slots[i]) * 60 - 60 

    sortDesc(waiting_time) 

    return waiting_time[m - 1]