Q$-2)(20$ pts$.)$ You are given an array of jobs where every job takes single $($i$.$e$\mathrm{.}1)$

unit of time. Also, every job has a deadline $($i$.$e$.$ latest time or date by which

something should be completed$)$ and an associated profit if the job is finished

before the deadline. Thus, the minimum possible deadline for any job is $1.$ If

only one job can be scheduled at a time, the job sequencing problem is to

maximize total profit. Below is an example optimal solution for the given job

list:

Input: Five jobs with the following deadlines and profits

Output: The

maximum profit Job

sequence of jobs is

$a,c,e.$

a$)(10$ pts$.)$ Describe, in words, a greedy algorithm for the job sequencing

problem.

b$)(10$ pts$.)$ Prove that your greedy choice is optimal $($e$.$g$.$ proof by

contradiction$).$