# Job Scheduling Problem

Moderate
0/80
Average time to solve is 15m
Contributed by

## Problem statement

You are given a list of ‘N’ jobs which has to be performed. Each job is associated with a deadline and a profit if the job is completed before the deadline. Each job takes one unit of time to complete.

You are required to schedule the jobs in such a way that total profit will be maximized. Only one job can be scheduled at a time, and jobs can be scheduled at only integer moments of time greater than or equal to one.

For example-
``````Let there be three jobs ‘A’, ‘B’, and ‘C’-
•Profit and deadline associated with job ‘A’ being 20 and 1.
•Profit and deadline associated with job ‘B’ being 30 and 2.
•Profit and deadline associated with job ‘C’ being 40 and 2.

We will perform job ‘C’ at time t = 1 and job ‘B’ at time t = 2. The total profit will be 70. There is no other sequence of jobs which can fetch us a better overall profit.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 5
1 <= N <= 10 ^ 3
1 <= profit[i] <= 10 ^ 9

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````2
3
2 10
1 50
2 30
3
1 20
2 30
2 40
``````
##### Sample Output 1:
``````80
70
``````

#### Explanation for Sample 1:

``````The optimal job scheduling for the first test case will be-

•Job 2 at time t = 1
•Job 3 at time t = 2

The total profit, in this case, will be 50 + 30 = 80.

The optimal job scheduling for the second test case will be-

•Job 2 at time t = 1
•Job 3 at time t = 2

The total profit, in this case, will be 40 + 30 = 70.
``````
##### Sample Input 2 :
``````1
5
2 100
1 19
2 27
1 25
3 15
``````
##### Sample Output 2 :
``````142
``````
Console