USACO 4.2 (IOI'96) -— Job Processing
Difference between en1 and en2, changed 71 character(s)
I couldn't prove the greedy algorithm which used in the A part of [this](http://olympiads.win.tue.nl/ioi/ioi96/contest/ioi96j.html) problem, so I looked it up on the internet and found ([this)[](http://blog.m-s-t.org/2012/12/27/usaco-4-2-job-processing-analysis/]). There is a proof there, but I think that it's incomplete. Specifically, it doesn't prove subproblem needs to be solved optimally for problem to be solved optimally. Thanks for help in advance.↵
↵
Also, I'm really bad at greedy algorithms. Is there any text on proof techniques for greedy algorithms, must-solve problems, or other important stuff on greedy algorithms you know?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English determinism 2015-07-02 16:31:26 3 Tiny change: 'thm which used in t' -> 'thm which is used in t'
en2 English determinism 2015-07-02 16:03:09 71
en1 English determinism 2015-07-02 16:02:37 612 Initial revision (published)