maximum-profit-in-job-scheduling.md

Maximum Profit in Job Scheduling

Mar 1, 2021 · 4 min read

Есть n задач, каждая из которых задана двумя отрезками времени: начало и конец, а так же некоторым «профитом», который получаешь при выполнении задачи.

Нужно найти набор задач, которые дадут максимальный профит.

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

Пример:

Есть несколько возможных расписаний:

Максимальный профит 20 + 70 + 60 = 150. Обратите внимание, что в красном варианте нельзя взять 100 или 70, потому что предыдущая задача «в процессе».

Задача на LeetCode.

Решение #

В принципе, мы можем проверить все возможные варианты расписаний. Однако, это будет очень долго, с учётом текущих ограничений — количество задач до 5 * 10^4.

Каким образом избежать полного перебора? Попробуем рассмотреть рекурсивную природу задачи, и это поможет в переходе к решению с динамическим программированием.

В рекурсии важны две вещи:

• базовый случай
• рекуррентное соотношение

Базовый случай, когда нет задач. Если нет задач — то и профит равен нулю. Если одна задача — взять её профит.

Что происходит если у нас есть две задачи? Есть выбор:

• взять следующую задачу в работу, пристегнув её в текущее расписание (если можно);
• не брать следующую задачу в текущее расписание, а попробовать строить новое со следующей задачи.

Что если у нас три, четыре, n задач? В этот момент мы вычислили максимальный профит для n - 1 задач. И можно это использовать!

/**
 * Вычисляет максимальный профит
 * для «хвоста» списка задач,
 * где n — длина хвоста.
 */
function getMaxProfit(n) {
  // базовый случай,
  // нет доступных задач
  if (n === TASKS_LEN) {
    return 0;
  }
  // есть два возможных варианта:
  return Math.max(
    // возьмем текущую задачу в расписание,
    // и попробуем пристегнуть к ней следующий
    // доступный по времени слот
    profitOfTask(n) + getMaxProfit(findNextSlotAvailable(n)),
    // не будем брать текущую задачу в расписание,
    // вместо этого начнём строить новое
    // со следующей задачи
    getMaxProfit(n + 1)
  );
}

Количество узлов в таком дереве вызовов будет расти довольно быстро, с учётом того, что мы создаём по два новых вызова в каждом следующем — O(2^n).

Здесь на помощь приходит динамическое программирование, или мемоизация. Вместо того, чтобы пересчитывать одни и те же результаты, но разными путями в дереве вызовов, можно просто закешировать результат для каждого n.

Грубо говоря, если максимальный профит был вычислен один раз, то «максимальнее» он уже не станет, по определению.

Таски задаются трёмя разными массивами: startTime, endTime и profit. Это не очень удобно, поэтому сперва соберём все в один массив с удобными структурами.

function buildNodesList() {
  const nodes = [];
  const len = startTime.length;

  for (let i = 0; i < len; i++) {
    nodes.push({ s: startTime[i], e: endTime[i], p: profit[i] });
  }
  return nodes;
}

Так же удобно его отсортировать по времени старта задачи, чтобы быстрее было искать «следующий доступный слот».

function findNextSlotAvailable(start) {
  // начинаем поиск следующего доступного слота
  // со start + 1,
  // ищем пока не найдётся первый таск,
  // который не пересекается с текущим
  for (let i = start + 1; i < len; i++) {
    if (nodes[i].s >= nodes[start].e) {
      return i;
    }
  }
  return len;
}

Всё вместе.

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number[]} profit
 * @return {number}
 */
var jobScheduling = function(startTime, endTime, profit) {
  const TASKS_LEN = startTime.length;

  // преобразуем в список узлов для удобства
  const nodes = buildNodesList();

  // отсортируем, чтобы удобнее искать
  // следующий доступный таск
  nodes.sort((a, b) => a.s - b.s);

  // для мемоизации
  const dp = new Array(TASKS_LEN).fill(0);

  // рекурсивно возвращает максимальный профит
  // для суффикса начиная с start
  function getMaxProfit(start) {
    // базовый случай,
    // суффикс длины ноль,
    // то есть нет доступных задач
    if (start === TASKS_LEN) {
      return 0;
    }
    // попали в кеш
    if (dp[start]) {
      return dp[start];
    }
    dp[start] = Math.max(
      nodes[start].p + getMaxProfit(findNextSlotAvailable(start)),
      getMaxProfit(start + 1)
    );
    return dp[start];
  }
  // вспомогателные функции,
  // описанные ранее
  function buildNodesList() {
    const nodes = [];
    for (let i = 0; i < TASKS_LEN; i++) {
      nodes.push({ s: startTime[i], e: endTime[i], p: profit[i] });
    }
    return nodes;
  }
  function findNextSlotAvailable(start) {
    for (let i = start + 1; i < TASKS_LEN; i++) {
      if (nodes[i].s >= nodes[start].e) {
        return i;
      }
    }
    return TASKS_LEN;
  }
  // чтобы получить ответ на задачу,
  // нужно вызвать для суффикса размером
  // с изначальный массив
  return getMaxProfit(0);
};

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.