# data structures – Need some help in designing this greedy algorithm

There are n jobs {J1, J2, . . . , Jn} with durations {a1, a2, . . . , an} ∈ N and deadlines d1, d2, . . . , dn ∈ N respectively. All the jobs are available at the beginning (that is at time 0). If a job J’
is completed at time t’ with t’ > d’, then the penalty u’ incurred for job J’ is −1; if t’ < d’, then u’ = 1 (which is an award). There’s only one machine. So, you cannot process more than one jobs simultaneously. Every job, once started, must run till it finishes. The goal is to find the schedule for these n jobs (that is a sequence according to which these n jobs will be performed) which maximizes $$Sigma_{i=1}^nui$$

I got this problem as an interview question and was blank all the way. I’ve been told that the optimal algorithm is greedy. I’ve tried sorting by deadlines and by durations none of which was optimal.