We have a set of jobs $J_i = (a_i, b_i)$ where all the $a_i,b_i \ge 0$. We want to find the permutation $\pi$ which minimises $$\max_j \left\{ b_{\pi(j)} + \sum_{k \le j}a_{\pi(k)} \right\}$$
Suppose we have proven that for all job sets $X$ of size no greater than $n$ the permutation which sorts the jobs by descending $b_i$ breaking ties by descending $a_i$ is an optimal solution (bearing in mind that there may be more than one optimal solution). (Call this ordering doubly-reverse-lexicographical because it sorts in descending order starting from the right).
Consider a job set $Y$ of size $n+1$ whose "worst" job is $J_{n+1}$, and suppose that there is no optimal solution in which this job comes first. Of the optimal solutions select one which puts $J_{n+1}$ as early as possible, in position $j^* = \pi^{-1}(n+1) > 0$. Now, which $j$ maximises the expression above (i.e. which job finishes last)?
Given that $b_{\pi(j^*)}$ is maximal by construction and the sum is non-decreasing the maximising $j$ must be $\ge j^*$. Also, if the maximising $j > j^*$ we can move $J_{n+1}$ to the start without affecting the optimality, so by contradiction that's impossible. We're forced to conclude that $J_{n+1}$ is the job which finishes last.
Now consider what happens if we swap it with the job before it. Call that job $J_p$ for previous. $J_p$'s finishing time increases from $b_p + \sum_{k < j^*}a_{\pi(k)}$ to $b_p + \sum_{k \le j^*}a_{\pi(k)} \le b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ and $J_{n+1}$'s finishing time decreases from $b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ to $b_{n+1} + \sum_{k \le j^* \wedge k \ne j^*-1}a_{\pi(k)}$ so we have a contradiction with this being an optimal solution which puts $J_{n+1}$ as early as possible.
We've now proven that there is an optimal solution for $Y$ in which $J_{n+1}$ comes first. Either some of these optimal solutions allow for the rest of the jobs to be ordered non-optimally because the worst job is so bad that it doesn't matter – in which case putting them in an optimal ordering will give an optimal ordering – or the rest of the jobs must be optimally ordered to get an optimal ordering. In either case we can apply our strong inductive presupposition to say that there is an optimal ordering which is doubly-reverse-lexicographical.
The base case of only one job is trivial.
The greedy algorithm isn't always optimal, but it depends on the size of the coins used. For example, consider using coins of size 10, 9, and 1. If you use the greedly algorithm to measure 18, you use 8 1s and 1 10, instead of an optimal 2 9s.
On the other hand, if each coin value is an integer multiple if the next smallest coin value, the greedy algorithm will be optimal. This is not quite the situation we are in, because dimes and quarters differ by a factor of 2.5, but my intuition says this will still not be enough to mess up the optimality of the greedy algorithm.
However, if you get rid of nickels, this changes, because 30 cents is 3 dimes but a quarter and five pennies. Without nickels, no optimal solution to a coin problem will use more than four dimes (why?), But with nickels, an optimal solution won't use more than two dimes. Is this fact enough to show the greedy algorithm is optimal with usual coin amounts?
Best Answer
You need to show the whole problem-we don't have access to Example 7. What is the criterion for "optimum"? Is it the most talks scheduled without overlap, the highest utilization of the hall, or what? You are probably expected to show a list of talks, show what the greedy algorithm produces, and show a better solution (according to the criterion for optimum). Do the talks come with times they have to be given, or are you setting that. This can come from the order you consider the talks-you might scatter a few at various times of the day, preventing many others from being scheduled. If the talks cannot be moved in time, you might schedule a whole batch from the hour to hour plus 5 minutes (only 5 min long), while you have a bunch of hour talks that don't fit any more. If you had scheduled the hours first, you would use the hall all day.