Proof for optimal interval scheduling using a Greedy Approach You are given a set of n jobs, where each job j is associated with a size
  s(how much time it takes to process the job) and a weight w(how important the
  job is). Suppose you have only one machine that can process one unit of jobs per
  time slot. Assume all jobs are given at time t = 0 and are to be processed one by one using this machine. Let C > to be the time that job j is completed. The goal is
  to find a schedule (of all the jobs) that minimizes the weighted completion time, i.Σ(j=1 to n) wj * CjApproach 1: Process Jobs according to the highest weight firstApproach 2: Process jobs in ascending order of their sizeApproach 3: Process jobs in descending order of their density (w/s)


So basically, I need to find out which approach is optimal and why the other 2 wouldn't work. My understanding is as follows:Approach 1 wouldn't be optimal if the higher weights(w) have a greater size(s).Approach 3 wouldn't work if the weight was equal to the size in case of all the jobs. If w=s for all the jobs, you wouldn't be able to determine what to chose first.Hence, my answer is that Approach 2 would be the optimal choice out of the 3 as it focuses on minimizing w*c. Is this answer correct? Is there a better way to prove why approach 2 is the optimal choice in this question?
Let's consider two jobs in the sequence you obtained:


$A$, of weight $w_A$ begins at $t_0$ and finish at $t_0 + s_A$
$B$ coming just after $A$, of weight $w_B$ begins at $t_0 + s_A$ and finish at $t_0 + s_A + s_B$


If we compute only $K_{A, B}$ the contribution of $A$ and $B$ in $K = \sum_j w_j C_j$:

$K_{A, B} = w_A (t_0 + s_A) + w_B (t_0 + s_A + s_B)$

If A and B are inversed in the sequence, we have $K'_{A, B}$:

$K'_{A, B} = w_A (t_0 + s_A + s_B) + w_B (t_0 + s_B)$

The difference is:

$\Delta K_{A, B} = K'_{A, B} - K_{A, B}$

$= w_A s_B - w_B s_A$

$= (w_A/s_A - w_B/s_B) \times (s_A s_B)$

The switch should be done if and only if $\Delta K_{A, B}$ is negative in order to minimize $K$. Only the approach 3 provides you a sequence where no more switch is worth.

If two jobs have the same $w/s$ ratio, just take them in any order, the final $K$ would remain unchanged.