Алгоритм планирования работы с крайним сроком и временем выполнения

Question

Учитывая массив заданий, в которых каждое задание имеет конечный срок (d_i> 0) и связанное с ним время выполнения (e_i> 0), то есть , нам задан массив (d_i, e_i), мы можем найти расположение рабочих мест, чтобы все они могли быть запланированы. Ответ может быть более чем возможным, любой будет достаточным.

например. {(3,1), (3,2), (7,3)} {J1, J2, J3} Ответ может быть одним из них {J1, J2, J3} или {J2, J1, J3}

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

Редактировать: Не более одной работы может выполняться одновременно.

Answer 1

Подсказка: после того, как вы успешно выполнили задание k начальных заданий, можно найти удовлетворительное полное расписание, только если есть следующее задание, время выполнения которого добавлено к текущему времени после того, как k предыдущих заданий меньше или равно время окончания следующей работы. Можете ли вы понять, почему всегда выбирать следующую работу с самым ранним сроком на каждом этапе выбора задания, будет определять, есть ли или нет, и если да, то даст точное решение? Дайте мне знать, если вы хотите получить более подробную информацию о том, как это доказать, но, надеюсь, вы можете увидеть это самостоятельно, когда я указал, что такое правильное жадное решение.

ОБНОВЛЕНИЕ: Дальнейший намек: предположим, что у вас есть удовлетворительное задание, когда два последовательных задания выходят из строя в соответствии с их крайними сроками (это просто означает, что общий порядок заданий не соответствует порядку в соответствии с крайними сроками). Затем можно закончить обе эти задания до более раннего срока в два крайних срока. Таким образом, также возможно завершить оба задания до более позднего срока, путем замены заданий, которые по-прежнему будут удовлетворительным заданием, потому что по предположению вы закончите более раннее задание на крайний срок до того, как вы закончили его, по предположению, и позднее крайний срок для этих двух позже, чем в более ранний срок, и ранее все еще можно было найти удовлетворительное задание.

Таким образом, если удовлетворительное присваивание существует, то существует еще один, который существует там, где задания упорядочены в соответствии с их крайними сроками. I., жадная стратегия всегда найдет удовлетворительное задание, если оно существует - в противном случае решения нет.

Answer 2

АО (NlogN) Жадный подход, основанный на структуре кучи данных

---

вход массив работы

struct Job 
{ 
char id; 
int deadLine; 
int profit; 
} 

---

Алгоритм псевдокода:

1.Sort the input jobArray in non-decresing order of deadLine. 
2.create a maxHeap (will consists of job).Basis of Comparison is profit 
3.let n=length of jobArray 
     initialize time=jobArray[n-1].deadLine 
       index=n-1 
4.while index>=0 && jobArray[index].deadLine >= time 
     4a) insert(maxHeap,jobArray[index]) 
     4b) index=index-1 
5. j=removeMax(maxHeap) 
    print j.id 
    time=time-1 
6.if time > 0 
    goto step 4. 
else 
    return ; 

В этом будет печатать задания в обратном порядке. Его можно изменить для печати в правильном порядке;