Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. The job sequencing problem is to maximize total profit if only one job can be scheduled at a time. Below is an example output for the optimal solution to this problem.

Input: Five Jobs with the following deadlines and profits

JobID	Deadline	Profit
a	2	100
b	1	19
c	2	27
d	1	25
e	3	15

Output: Following is the maximum profit sequence of jobs c, a, e

(a) Describe, in words, a greedy algorithm for the job sequencing problem.

(b) Prove that your greedy choice is optimal (e.g. proof by contradiction).