Алгоритм бинарного поиска для максимизации значений

Question

Мне была назначена эта проблема, я должен был решить:

В определенном бассейне есть много руководств. Поэтому правила использования очень строгие:

Свободные временные интервалы составляют только одну минуту. После использования свободного слота мы должны подождать не менее x секунд, прежде чем использовать другой слот. У вас есть список бесплатных слотов, и вы хотите поплавать как минимум за m минут. Каков максимальный x, что позволяет?

Ввод

Ввод состоит из нескольких случаев. Каждое дело начинается с количества минут m и количества слотов n, а затем n троек H:M:S, указывая, что есть полоса, свободная в течение одной минуты, начиная с H:M:S. Предположим, 2 ≤ m ≤ n ≤ 1000, что часы находятся между 00:00:00 и 23:59:00 и что между временными интервалами нет совпадений. Окончательная запись отмечена специальным футляром с m = n = 0.

Выход

Для каждого случая, печатать максимальную 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

Это не требует никакого поиска вообще. Преобразовать список из свободных временных интервалов в список ожидания времени между канальными интервалами в секундах (примите во внимание, вы плавание в течение одной минуты):

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]