# Finding an optimal schedule [Dynamic Programming]

I'm reading through an algorithm textbook and I've come across yet another problem that I'm stuck on. I'm looking for some help solving it and if anyone could provide some similar, already-existing, problems that I could reference to follow similar steps, that'd be great.

This is the problem:

The part $(a)$ already gives an algorithm for part $(b)$. So let's focus on proving part $(a)$.
Suppose we have some optimal scheduling with $n$ jobs. Consider the very first job scheduled which does not have the earliest deadline. Let this be the $k$th job $J_k$.
Since all jobs before job $J_k$ have earliest deadline and job $J_k$ is the very first job whose deadline isn't the earliest, there must exist some job $J_k'$ whose deadline is earlier than job $J_k$. But this job can start immediately after job $J_{k-1}$ because job $J_{k-1}$ has the earliest deadline. In fact, we can replace job $J_k$ with job $J_k'$. And still schedule $n$ jobs.
For part $(b)$, simply sort all jobs by deadline in $O(n\log{n})$ and pick the earliest each time as long as the job can be run. This is a classic greedy algorithm.