a)For the job scheduling problem consider the following algorithm:

Repeat until no more jobs left:

Let J be the job that overlaps with the fewest jobs.

Choose J and remove all jobs that overlap with J.

Show that the algorithm above is not correct. Hint: Give an example where the algorithm does not select the largest possible set. Explain what the algorithm chooses and then show there is a larger set.