title: Proving the greedy solution to the weighted task scheduling problem
body: <p>I am attempting to prove <a href="https://www.youtube.com/watch?v=zPtI8q9gvX8" rel="nofollow noreferrer">the following algorithm</a> is fully correct (partial correctness + termination), but I can only seem to prove for arbitrary example inputs (not general ones).</p>
  <pre><code>Here is my pseudo-code:
  
  IN :Listofjobs J, maxindex n
  
  1:S ← an array indexed 0 to n, with null at each index 
  2:Sort J in non-increasing order of profits 
  3:for i from 0 to n
  4:Find the largest t such that S[t] = null and t ≤ J[i].deadline (if one exists) if an index t was found
  5: S[t] ← J[i]
  
  OUT: S maximizes the profit of scheduled jobs that can be done in n 1 unit of time blocks
  </code></pre>
  <p>So for example, I created a table with jobs and their associated attributes (deadlines and profit):</p>
  <pre><code>jOB        J1   J2  J3  J4  J5
  Deadline    2   1   3   2   1
  profit     62   100 20  40  20
  </code></pre>
  <p>From this example input, we'd be able to do J2,J1,J3 for a total profit of 182.</p>
  <p>Can someone help me form a more generic way of showing my pseudo-code algorithm is fully correct?</p>