Scheduling

You are given n jobs where each job takes one unit of time and i
th job provides a gain of gi
(gi > 0) if completed on or before its integer deadline di. All jobs can start as early as time
0. For instance, first job can start at time 0 and end at time 1 in an optimal schedule. (Note
that the algorithm generalizes to real number deadlines trivially so the restriction is for ease
of I/O 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. (The input jobs must be ordered in the descending order of gain as
shown.)
1 4 20
2 2 15
3 2 15
4 1 10
5 3 5
The expected output schedule and total gain are given below. You must additionally print
the input sorted by gain too as shown below for completeness.
Input Jobs, Deadlines and Gains (sorted by descending Gains)
1 4 20
2 2 15
3 2 15
4 1 10
5 3 5
Output Schedule by End Time (0 means not scheduled.)
1 4
2 2
3 1
4 0
5 3
Total Gain
55