title: Proof of optimality of a greedy solution to job sequencing
body: <p>In this <a href="http://www.geeksforgeeks.org/job-sequencing-problem-set-1-greedy-algorithm/" rel="noreferrer">Job Sequencing Problem</a>, how do we prove that the solution which greedy approach will provide is a optimal one? </p>
  
  <p>Moreover, I am also not able to figure out the O(n) solution as the author later is claiming</p>
  
  <blockquote>
    <p>It can be optimized to almost O(n) by using union-find data structure.</p>
  </blockquote>