Недавно я наткнулся на вопрос интервью, размещенный на 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 здесь!

Ссылка на другие вопросы по программированию —
Преобразование двоичного числа в связанном списке в целое число
Найти совершенные, недостаточные и избыточные числа
Найти сколько Воскресенье приходилось на первое число месяца для данного года