2
$\begingroup$

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:

Scheduling problem

$\endgroup$
2
$\begingroup$

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.
In this way, we can keep selecting the very first job which doesn't have the earliest deadline and keep replacing with the earliest. Since the number of job assignments is finite, we must stop at some point and at this point the number of jobs hasn't changed and the job assignments each have the earliest deadline.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.