Недавно я наткнулся на вопрос интервью, размещенный на Geeks For Geeks! Несмотря на то, что вопросы могут быть разными, первые раунды обычно представляют собой тесты по кодированию, и всегда полезно немного попрактиковаться в таких вопросах динамического программирования.
Даны три массива, называемые pickup, drop и tip. Найдите максимальную прибыль, которую может заработать курьер. Парень может обрабатывать только одну доставку за раз.
Пример: Он получает прибыль в размере 5 - 0 + 1 = 6
6 единиц, если 1-й заказ доставлен
Pickup: [0,2,9,10,11,12]
drop: [5,9,11,11,14,17]
подсказка:[1,2,3,2,2,1]
Эта программа выглядит как вариация «Максимальная прибыль при планировании работы»:
У нас есть три массива: start
, end
, profit
для N
заданий. Тогда программа должна вернуть максимальную прибыль, когда никакие две работы не пересекаются в одном и том же временном диапазоне, т. е. каждая запланированная работа должна быть выполнена с start[i]
по end[i]
с прибылью profit[i]
.
Example: Input: start = [2, 3, 4, 6, 7], end = [4,6,11,7,10] and profit =[30,30,200,80,70] Output: 180 How?: The elements chosen are the first, fourth, and fifth jobs. Thus, we will get the profit of 180 = 30 + 80 + 70.
Реализация с использованием JavaScript:
Сначала мы создаем массив объектов, используя заданные массивы start
, end
, profit
. Пример:
const myJobObject = [{ start: 2, end: 4, profit: 30 }]
Для этого мы создадим метод, который принимает массивы начала, конца и прибыли. Прокрутите их и сохраните все myJobObjects в массиве, как показано ниже:
const jobScheduling = (start, end, profit) => { const myJobObject = []; for (let i = 0; i<start.length; i++) { myJobObject.push({ start: start[i], end: end[i], profit: profit[i] }); } }
Это проблема жадного алгоритма, и в любой жадной задаче мы следуем методу решения проблемы, чтобы решить проблему на каждом этапе решения оптимально. Поэтому Мы хотим построить решение, которое даст нам оптимальное решение с немедленным эффектом!
Максимальная прибыль в планировании заданий аналогична Планированию взвешенных интервалов, где нам нужно запланировать непересекающиеся задачи максимального веса в заданный период времени.
Согласно анализу Планирование взвешенных интервалов, мы будем сортировать массив по времени окончания в порядке возрастания, т. е. самое раннее время окончания.
Итак, теперь мы отсортируем наш myJobObject
по времени окончания и добавим в наш кусок кода компаратор сортировки:
function sortObj(obj1, obj2) { return (obj1.end - obj2.end); } const jobScheduling = (start, end, profit) => { const myJobObject = []; for (let i = 0; i<start.length; i++) { myJobObject.push({ start: start[i], end: end[i], profit: profit[i] }); } //sort as per endtime myJobObject.sort(sortObj); }
Теперь нам нужно определить последнюю неконфликтную доставку (т. е. найти последнюю работу, которая не конфликтует с нашей текущей работой). Для этого мы выполним простой линейный поиск в нашем массиве объектов и вернем индекс следующего неконфликтующего задания:
function findLatestNonConflictDelivery(myJobObject, i) { for (let j=i-1; j>=0; j--) { if (myJobObject[j].end <= myJobObject[i].start) return j; } return -1; }
Теперь соберем части вместе и найдем максимальную прибыль:
function findMaxProfit(myJobObject){ let n = myJobObject.length; let maxProfit = []; //initializing first profit maxProfit[0] = myJobObject[0].profit; for (let i=1; i<n; i++) { let j = findLatestNonConflictDelivery(myJobObject, i); let profit = myJobObject[i].profit; if (j != -1) { //when next non conflicting job is found profit = maxProfit[j] + profit; } //we will store max maxProfit[i] = Math.max(profit, maxProfit[i-1]); } //we will store the result of the max profit let result = maxProfit[n-1]; return result; }
Вот и все.
Теперь потренируйтесь на платформе leetcode здесь!
Ссылка на другие вопросы по программированию —
Преобразование двоичного числа в связанном списке в целое число
Найти совершенные, недостаточные и избыточные числа
Найти сколько Воскресенье приходилось на первое число месяца для данного года