Эффективное планирование кабины - PullRequest
1 голос
/ 30 сентября 2019

Я столкнулся с этим техническим вопросом во время подготовки. Есть K такси. Поездка на такси занимает до 12 минут. Какое минимальное время потребуется, чтобы завершить N поездок с этими кабинами. Можно предположить, что между поездками нет времени ожидания, и разные такси могут совершать поездки одновременно. Может кто-нибудь предложить эффективный алгоритм для решения этой проблемы.

Пример:

Input:
N=3 K=2
K1 takes 1 minute, K2 takes 2 minutes

Output:
2 minutes

Explanation: Both cabs starts trip at t=0. At t=1, first cab starts third trip. So by t=2, required 3 trips will be completed

1 Ответ

3 голосов
/ 30 сентября 2019

Двоичный поиск кажется довольно интуитивным и простым. Давайте перефразируем вопрос:

Учитывая время t, вычислим максимальное количество поездок, которое можно предпринять.

Мы можем сделать это в O(K). Учтите, что каждая кабина i может совершить до t / k_i поездок за t время, и мы можем просто получить сумму всех t / k_i для каждого i, чтобы получить максимальное количество поездок, совершенных в tвремя. Это позволяет нам построить функцию, по которой мы можем выполнить бинарный поиск:

def f(time):
    n_trips = 0
    for trip_time in cabs:
        n_trips += time // trip_time
    return n_trips

Очевидно, из этого следует, что с увеличением количества времени количество поездок, которое мы можем совершить, также будет увеличиваться, поэтому f(x) не-снижение, что означает, что мы можем запустить бинарный поиск по нему.

Мы выполняем двоичный поиск минимума t, который дает N или более отключений в качестве вывода, и это можно сделать в O(KlogW), где W - это диапазон всех t, которые мыдолжен рассмотреть.

...