Задача определения последовательности заданий с использованием непересекающегося набора

Опубликовано: 12 Января, 2023

Дан набор из n заданий, где каждое задание i имеет крайний срок di >=1 и прибыль pi>=0. Одновременно может быть запланировано только одно задание. Каждое задание выполняется за 1 единицу времени. Мы получаем прибыль тогда и только тогда, когда работа выполнена в установленный срок. Задача состоит в том, чтобы найти подмножество работ, которое максимизирует прибыль.

Примеры:

Input: Four Jobs with following deadlines and profits
JobID Deadline Profit
   a      4      20
   b      1      10
   c      1      40
   d      1      30
Output: Following is maximum profit sequence of jobs:
       c, a

Input: Five Jobs with following deadlines and profits
JobID Deadline Profit
   a     2       100
   b     1       19
   c     2       27
   d     1       25
   e     3       15
Output: Following is maximum profit sequence of jobs:
       c, a, e

Жадное решение временной сложности O(n 2 ) уже обсуждалось здесь. Ниже приведен простой жадный алгоритм.

  1. Отсортируйте все работы в порядке убывания прибыли.
  2. Инициализируйте результирующую последовательность как первое задание в отсортированных заданиях.
  3. Выполните следующие действия для оставшихся n-1 заданий
    • Если текущее задание может вписаться в текущую последовательность результатов без нарушения крайнего срока, добавьте текущее задание к результату. В противном случае игнорировать текущую работу.

Дорогостоящей операцией в решении Greedy является выделение свободного слота для работы. Мы просматривали каждый слот для работы и назначали максимально возможный временной интервал (<крайний срок), который был доступен.
Что означает наибольший временной интервал?
Предположим, что задание J1 имеет крайний срок t = 5. Мы назначаем наибольший временной интервал, который свободен и меньше крайнего срока, т.е. 4-5 для этого задания. Теперь приходит другое задание J2 со сроком 5, поэтому отведенный временной интервал будет 3-4, поскольку 4-5 уже выделено заданию J1.
Зачем назначать наибольший временной интервал (свободный) для работы?
Теперь мы назначаем максимально возможный временной интервал, поскольку, если мы назначим временной интервал даже меньше доступного, тогда может быть какая-то другая работа, которая не уложится в срок.

Пример:
J1 со сроком d1 = 5, прибыль 40
J2 со сроком d2 = 1, прибыль 20
Предположим, что для задания J1 мы назначили временной интервал 0-1. Теперь задание J2 не может быть выполнено, так как мы будем выполнять задание J1 в течение этого временного интервала.
Использование непересекающегося набора для определения последовательности заданий
Все временные интервалы изначально являются индивидуальными наборами. Сначала найдем максимальный срок всех работ. Пусть максимальный срок равен m. Мы создаем m+1 индивидуальных наборов. Если заданию назначается временной интервал t, где t >= 0, то задание запланировано на [t-1, t]. Таким образом, набор со значением X представляет временной интервал [X-1, X].
Нам нужно отслеживать наибольший доступный временной интервал, который может быть выделен для данной работы с крайним сроком. Для этой цели мы используем родительский массив структур Disjoint Set Data. Корень дерева всегда является последним доступным слотом. Если для крайнего срока d нет доступного слота, тогда root будет равен 0. Ниже приведены подробные шаги.
Инициализировать непересекающийся набор: создает начальные непересекающиеся наборы.

// m is maximum deadline of a job
parent = new int[m + 1];

// Every node is a parent of itself
for (int i = 0; i ≤ m; i++)
    parent[i] = i;

Найти : поиск последнего доступного временного интервала.

// Returns the maximum available time slot
find(s)
{
    // Base case
    if (s == parent[s])
       return s;

    // Recursive call with path compression
    return parent[s] = find(parent[s]);
}

Союз :

 Merges two sets.  
// Makes u as parent of v.
union(u, v)
{
   // update the greatest available
   // free slot to u
   parent[v] = u;
}

Почему find возвращает последний доступный временной интервал?
Изначально все временные интервалы являются отдельными интервалами. Таким образом, возвращаемый временной интервал всегда максимален. Когда мы назначаем временной интервал «t» заданию, мы объединяем «t» с «t-1» таким образом, что «t-1» становится родителем «t». Для этого мы вызываем union(t-1, t). Это означает, что все будущие запросы для временного интервала t теперь будут возвращать последний временной интервал, доступный для набора, представленного t-1.

Реализация :
Ниже приведена реализация вышеуказанного алгоритма.

Сложность времени: O(N*log(D)), где N — общее количество заданий, а D — максимально возможный срок.
Пространственная сложность: O(D) Поскольку для непересекающегося множества был создан дополнительный массив размером D.

Эта статья предоставлена Чирагом Агарвалом. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по адресу review-team@geeksforgeeks.org. Посмотрите, как ваша статья появится на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

РЕКОМЕНДУЕМЫЕ СТАТЬИ