Task 51. Доставка заказов
UniLecsЗадача: Алисе и Бобу нужно подготовить и доставить N заказов.
Дано время t1 - время упаковки посылки Алисой, время t2 - время доставки посылки Бобом. Зная время t1, t2 вычислить наименьшее время, необходимое для выполнения всех заказов. За раз, Алиса и Боб могут доставить только один заказ.
Входные данные:
Дан двумерный массив, в первой строке – время упаковки каждого заказа Алисой, а во второй – время его доставки Бобом. (0 < t1, t2 ≤ 1000)
Написать функцию, ктр вернет наименьшее время доставки всех заказов.
Например,
4 4 30 6 2
5 1 4 30 3
Вывод:
47
Идея: это классическая задача про два станка, которые последовательно обрабатывают детали.
Пусть время упаковки i-го заказа Алисой равно Ai, а время его доставки Бобом равно Bi. Ищем наименьшее значение среди чисел Ai и Bi (i = 1, n). Если наименьшим значением будет Ai, то ставим i - ый заказ на обработку первым, если Bi – то последним. После этого удаляем i - ый заказ из списка. Повторяем описанный процесс для оставшихся (n – 1)-го подарка.
Отметим, что заказ не может быть доставлен Бобом пока он не будет упакован Алисой. Если Бобу доступно несколько заказов для доставки, которые уже упакованы Алисой, то будем пользоваться следующим правилом: порядки упаковки закзов Алисой и доставки Бобом должны совпадать.
Разберем работу алгоритма на примере, ктр мы привели в условии задачи:
Начало очереди и её окончание имеют соответственно номера 1 и 5. Первый локальный минимум обеих массивов равен 1 и находится во втором массиве, поэтому ставим заказ № 2 в конец очереди на выполнение работ, то есть на место 5 (меняем местами заказы под номерами 2 и 5):
При этом найденный заказ номер 2 из дальнейшего рассмотрения исключаем, что аналогично тому, что мы уменьшим на единицу номер хвоста очереди, он теперь равен 4. Ищем новый локальный минимум в обеих массивах, он равен 2 и находится в первом массиве, поэтому ставим заказ № 2 в начало очереди на выполнение работ, соответственно меняем заказы 1 и 2 местами, и увеличиваем начало очереди:
Среди оставшихся заказов с номера 2 по 4 ищем новый локальный минимум. Он находится в первом массиве, поэтому ставим его в начало очереди на выполнение работ, а начало очереди увеличиваем на единицу, оно станет равно 3:
Новый локальный минимум 4 находится во втором массиве, поэтому ставим его в конец очереди:
Далее нужно посчитать полученное суммарное время, т.к. Боб не может доставить заказ раньше, чем Алиса закончит его упаковку. Очевидно, что для минимизации временных затрат Алиса должна работать непрерывно, пока не упакует все заказы, после чего сможет отдохнуть. Также очевидно, что Боб не сможет приступить к доставке очередного заказа, пока он не упакован Алисой, поэтому ему точно придётся дождаться окончания упаковки 1-го заказа и далее, возможно, придётся также дожидаться окончания упаковки очередного заказа в сформированной ранее очереди выполнения работ.
Реализация: Обозначим через sum наименьшее время доставки всех заказов. Тогда если, например, имеется только один заказ, то sum = A1+ B1. В случае двух заказов sum = A1 + max(A2, B1) + B2
https://gist.github.com/unilecs/a776c0b04134776cd1ff7aed145dbf8c
Тест: