Проблема последовательности заданий с использованием TreeSet в JAVA

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

Дан массив заданий, где каждое задание имеет крайний срок и связанную с ним прибыль (если задание выполнено до крайнего срока). Также известно, что каждая работа занимает одну единицу времени, поэтому минимально возможный крайний срок для любой работы равен 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

Ниже приведен пошаговый алгоритм решения задачи с помощью TreeSet в Java:

  1. Отсортируйте все рабочие места в соответствии с их соответствующей прибылью в порядке убывания.
  2. Создайте TreeSet и вставьте все целые числа от 0 до n-1.
  3. Обходим массив заданий и для i-го задания
    • Найдите временной интервал 'x' в TreeSet с максимальным значением, которое меньше крайнего срока i- го задания.
    • Если какое-либо значение существует, включите это задание в ответ и удалите «x» из TreeSet.
    • В противном случае проверьте оставшиеся задания.

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

Временная сложность : O (N * log (N))
Вспомогательное пространство : O(N)