Постановка задачи:
Дан массив заданий, где у каждой работы есть крайний срок и соответствующая прибыль, если работа завершена до крайнего срока. Также указано, что каждое задание занимает одну единицу времени, поэтому минимально возможный крайний срок для любого задания равен 1. Как максимизировать общую прибыль, если одновременно можно запланировать только одно задание.
Решение:
Учитывая массив
arr = [(5, 100), (1, 19), (2, 27), (1, 25), (3, 30), (3, 28)]
Здесь каждый элемент массива представляет собой пару значений, где первое значение - это крайний срок выполнения задания, а второе значение - присвоенная ему прибыль.
Теперь давайте просто создадим функцию jobSequenceDeadline, и она будет принимать только один аргумент, то есть только переменную массива.
def jobSequenceDeadline(arr): # entire logic
Теперь я собираюсь решить эту проблему шаг за шагом, чтобы ее было легко понять.
Шаг 1. Отсортируйте массив по убыванию прибыли.
Каждый элемент массива представляет задание, а каждое задание содержит крайний срок и свою прибыль.
Итак, массив, который у нас есть, представляет собой кортеж из двух значений, и нам нужно отсортировать его в порядке убывания его прибыли.
def sortPara(val): return val[1] arr.sort(key = sortPara, reverse = True)
Сортировка займет O (nlogn)
Теперь массив будет выглядеть так
arr = [(5, 100), (3, 30), (3, 28), (2, 27), (1, 25), (1, 19)]
Шаг 2: Найдите максимальный крайний срок среди всех заданных крайних сроков, а также создайте массив размером n + 1 и присвойте ему начальное значение, равное нулю, где n - максимальный крайний срок.
maxDeadline = max(arr)[0] job = [0 for i in range(maxDeadline + 1)]
Эта операция займет O (n)
Шаг 3. Затем создайте словарь или хеш-карту и подсчитайте, когда наступил срок.
В данном массиве наступление крайнего срока 5 равно 1, наступление крайнего срока 3 равно 2, наступление крайнего срока 2 равно 1 и наступление крайнего срока 1 равно 2.
deadlines = {}
for i in range(0, len(arr)):
if arr[i][0] in deadlines:
deadlines[arr[i][0]] += 1
else:
deadlines[arr[i][0]] = 1
Это также займет O (n)
ПРИМЕЧАНИЕ. оператор in - O (1) для словарей и задается в python.
Шаг 4. Проверьте пропущенный срок и обработайте его соответствующим образом.
Этот шаг может показаться сложным, и мы постараемся упростить его.
Итак, в данном массиве у нас есть задание с крайними сроками 1, 2, 3, 5, а у нас нет крайнего срока 4.
Теперь поймите, что максимальное количество работ, которое мы можем выполнить, равно максимальному сроку, который у нас есть.
В данном конкретном случае максимальный срок составляет 5, поэтому максимальное количество работ, которые мы можем выполнить, равно 5.
Но на самом деле, с данным массивом невозможно выполнить 5 заданий, здесь мы можем выполнить только 4 задания.
Теперь давайте просто попробуем понять, когда мы можем выполнять максимальное количество работ, а когда нет.
- Когда у нас есть все сроки, мы, конечно, можем выполнить максимальное количество работ.
- Если мы пропустим какой-либо крайний срок, то задания, срок выполнения которых превышает пропущенный, выполняются как минимум более одного раза.
В этом конкретном случае мы пропускаем крайний срок 4, а количество заданий с крайним сроком больше 4 составляет всего 1, а для выполнения максимального количества заданий нам нужно как минимум больше 1.
Так что в этом случае мы не можем выполнить максимальное количество работ.
req = []
for key in range(1, maxDeadline + 1):
if key not in deadlines:
req.append(key)
elif deadlines[key] > 1 and len(req) > 0:
req.pop()
Эта функция найдет недостающий дедлайн, из-за которого мы не можем выполнить максимальное количество заданий.
В этом случае получаем
req = [4]
Эта операция также займет O (n)
ПРИМЕЧАНИЕ. оператор in - O (1) для словарей и задается в python.
Шаг 5. Позвольте найти максимально возможное количество вакансий.
Таким образом, максимальное количество возможных заданий - это разница между максимальным сроком и длиной массива req.
Здесь максимальный крайний срок представляет собой максимальное количество возможных заданий, а длина массива req представляет количество возможностей, которые невозможны, потому что у нас нет никаких процессов для заполнения крайних сроков, доступных в массиве req.
total_possible_job = maxDeadline - len(req)
Шаг 6: Последний шаг - давайте просто найдем возможные вакансии
Итак, давайте просто разберемся с логикой, используемой здесь для поиска рабочих мест таким образом, чтобы общая прибыль была максимальной.
Итак, мы уже отсортировали массив по убыванию по прибыльности.
Теперь мы понимаем роль созданного ранее массива заданий.
count = 0
ans = []
for i in range(len(arr)):
if count >= total_possible_job:
break
elif job[arr[i][0]] < arr[i][0]:
count += 1
job[arr[i][0]] += 1
ans.append(arr[i])
Здесь мы в основном делаем это:
job[1] < 1 -> job[1] can have one job job[2] < 2 -> job[2] can have two job job[3] < 3 -> job[3] can have three job job[4] < 4 -> job[4] can have four job job[5] < 5 -> job[5] can have five job
И когда count станет равным total_possible_job, мы прервем цикл и вернем массив ans.
ans = [(5, 100), (3, 30), (3, 28), (2, 27)]
Эта операция также займет O (n)
Окончательная сложность
O(nlogn) + O(n) + O(n) + O(n) + O(n) = O(nlogn)
Таким образом, общая сложность равна O (nlogn)
Полный код будет выглядеть так.
Посетите Algo Mart, чтобы увидеть интересные вопросы по кодированию интервью.
