# Maximal feasible job set,

or 1||ΣU_{j}

We are given *n* jobs. Each job *j* has a
processing
time *p*_{j} and a duedate *d*_{j}.
We wish to find a schedule
for a single machine, which minimizes the number of jobs which complete after their due-date.
In fact we search for a maximal feasible job set.
Algorithm by **Hogdson**:
We initialise S to be the empty job set.
We processe jobs j in order of increasing due-dates.
We add j to S, and if it becomes infeasible, we remove the job i with the greatest processing time (which might be j itself). To check feasibility of S, we simply keep track of the total processing time and compare it with the due-date of job j.

## Input

## Output