Given a list of **Jobs** with their **deadline** and **profit** earned on completion, find the maximum profit earned by executing the Jobs within the specified deadlines.

Assume that each job takes one unit of time to complete, and a job can't run beyond its deadline.

Also, only a single job will be run at a time.

##### Example 1: Job Sequencing Problem

Input:

Tasks | Deadlines | Profit |
---|---|---|

a | 4 | 20 |

b | 1 | 10 |

c | 1 | 40 |

d | 1 | 30 |

Output: **c,a**

##### Example 2: Job Sequencing Problem

Input:

Tasks | Deadlines | Profit |
---|---|---|

a | 2 | 100 |

b | 1 | 19 |

c | 2 | 27 |

d | 1 | 25 |

e | 3 | 15 |

Output: **c,a,e**

## Solutions

### Method 1: Greedy

The greedy algorithm suggest to Iterate on jobs in decreasing order of profit and for each job find a time slot "T", such that slot is empty and T < deadline and T is greatest.

**1)** Sort all jobs in decreasing order of profit.

**2)** Iterate on jobs and for each job find a time slot "T", such that slot is empty and T < Deadline and T is greatest.

**3)** If slot is empty, put the job in his slot and mark this slot filled, else if no such slot - "T" exists, then ignore the job.

##### Complexity

**O(n2)**.