Проблема последовательности заданий с использованием 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:
- Отсортируйте все рабочие места в соответствии с их соответствующей прибылью в порядке убывания.
- Создайте TreeSet и вставьте все целые числа от 0 до n-1.
- Обходим массив заданий и для i-го задания
- Найдите временной интервал 'x' в TreeSet с максимальным значением, которое меньше крайнего срока i- го задания.
- Если какое-либо значение существует, включите это задание в ответ и удалите «x» из TreeSet.
- В противном случае проверьте оставшиеся задания.
Ниже приведена реализация вышеуказанного алгоритма:
Временная сложность : O (N * log (N))
Вспомогательное пространство : O(N)