we have not to implement in any language we have to design algorithm

Design and implement an efficient algorithm to find a schedule (determining jobs and their end times) that maximizes the gain. (The start times are implicit.) Also provide a clear informal argument of correctness and computational complexity.

You are given n jobs where each job takes one unit of time and ith job provides a gain of gi (gi > 0) if completed on or before its integer deadline di. All events can start as early as time 0. For instance, first job can start at time and end at time I in an optimal schedule. (Note that the algorithm generalizes to real number deadlines trivially so the restriction is for ease of 1/0 and enabling reliable equality checks.) Design and implement an efficient algorithm to find a schedule (determining jobs and their end times) that maximizes the gain. (The start times are implicit.) Also provide a clear informal argument of correctness and computational complexity. Assume that the input is given as a sequence of lines providing job id, job deadline, and job gain in that order. (While I have ordered the jobs on the basis of gain for ease of reading, that is not required of the input.) 1 4 20 2 3 15 3 4 15 4 3 10 5 1 5 The expected output schedule and profit is given below. You must additionally output the input too as shown below. Input Jobs, Deadlines and Gains sorted by Gains 1 4 20 2 3 15 3 4 15 4 3 10 51 5 Output Schedule by End Time (O means not scheduled.) 1 4 2 3 3 2 4 0 5 1 Total Gain 55 You are given n jobs where each job takes one unit of time and ith job provides a gain of gi (gi > 0) if completed on or before its integer deadline di. All events can start as early as time 0. For instance, first job can start at time and end at time I in an optimal schedule. (Note that the algorithm generalizes to real number deadlines trivially so the restriction is for ease of 1/0 and enabling reliable equality checks.) Design and implement an efficient algorithm to find a schedule (determining jobs and their end times) that maximizes the gain. (The start times are implicit.) Also provide a clear informal argument of correctness and computational complexity. Assume that the input is given as a sequence of lines providing job id, job deadline, and job gain in that order. (While I have ordered the jobs on the basis of gain for ease of reading, that is not required of the input.) 1 4 20 2 3 15 3 4 15 4 3 10 5 1 5 The expected output schedule and profit is given below. You must additionally output the input too as shown below. Input Jobs, Deadlines and Gains sorted by Gains 1 4 20 2 3 15 3 4 15 4 3 10 51 5 Output Schedule by End Time (O means not scheduled.) 1 4 2 3 3 2 4 0 5 1 Total Gain 55