Geek Answers Handbook

Proof of the optimality of a greedy solution for a work sequence

In this problem of job ordering , how do we prove that the solution that the greedy approach provides is optimal?

In addition, I also cannot determine the solution O (n), since later the author claims that

It can be optimized almost to O (n) using the union-find data structure.

+5
source share
4 answers

The optimality of the greedy solution can be seen by the exchange argument as follows. Without loss of generality, suppose that all profits are different and that jobs are sorted in descending order of profit.

S. , . , S1 - . i I_i:=[0,min(n,deadline(i))] ( ). , i, ( , , ). i I_i.

, .

S S' propoerties.

  • S' S, .
  • i S i I_i .
  • i S i I_i.
  • S' , S.

, S* . S - , . , S 2 3 . i - , S, S*. pos - i S. pos S*, S* , i, S*. pos S*, i' at pos S* , i, i' pos S. , , i. , i S*, S*.

+3

  • . , . ? , - , , . , ( ). . , , , .

  • , O(n ^ 2). . union-find , , , , . - O(n log n).

+1

2 4 , 1 , 3. "" : , .

O (n ^ 2) O (n), , . "" , , - O (nlogn) - , - O (n) - O (nlogn).

, - , radix, .

0

This evidence is not complete. Namely, the sentence "the work of i'at pos in S * cannot bring more profit than I" is not proven, and I think it cannot be. Be that as it may, it can be proved that this statement is true, even if work i brings me profit greater than or equal to i. ''

for full proof see http://ggn.dronacharya.info/CSEDept/Downloads/QuestionBank/Even/VI%20sem/ADA/Section-B/job-scheduling1.pdf

0
source

More articles:


All Articles