値を最大化するためのバイナリ検索アルゴリズム

Question

私はこの問題を割り当てられました。私は解決しなければなりません：

特定のスイミングプールにはたくさんのガイド付きアクティビティがあります。したがって、使用規則は非常に厳格です。

フリータイムスロットはわずか1分です。フリースロットを使用した後、別のスロットを使用する前に少なくともx秒待つ必要があります。空きスロットのリストがあり、少なくともm分間泳ぎたいと思う。それを可能にする最大数はxですか？

入力

入力はいくつかのケースから成ります。すべての場合は、分の数がm、スロットの数がnで始まり、nトリプルH:M:Sが続き、これは1分無料のレーンがH:M:Sから始まることを示しています。 2 ≤ m ≤ n ≤ 1000とし、時間が00:00:00と23:59:00の間であり、タイムスロット間に重複がないと仮定します。最後のエントリには、m = n = 0という特殊なケースが付いています。

すべてのケースに対する出力

、M分以上の総浴時間を許容最大xを印刷します。

変数xを最大化するためにバイナリ検索を使用して実装することはできますか？問題の

出力：

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

これは、すべての任意の検索を必要としません。秒単位のタイムスロット間の待ち時間のリストに空きタイムスロットからリストを変換（あなたは1分間泳いだ考慮して）：

waiting_time[] 

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

ソート待機時間のリストを

sortDesc(waiting_time) 

m - 1回を待たなければならないので、x待ち時間が少なくとも同等に長くなるように、xを選択する必要があります。最大でxを検索しているので、待ち時間はxと正確に同じでなければなりません。これは、配列内のm - 1要素です。一緒にすべてを置く

：

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]