Job Scheduling Problem

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
AmazonCultfitAtlassian

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 )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains a single space-separated integers ‘N’, denoting the total number of jobs.

The next ‘N’ lines contain two space-separated integers, 'deadline[i]' and 'profit[i]' denoting the deadline and the profit associated with the 'i-th' job.
Output Format : 
For each test case, print the maximum profit after scheduling all the jobs in an optimal manner.

Output for each test case will be printed in a new line.
Note 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 10 ^ 3
1 <= deadline[i] <= N
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
Hint

Sort the jobs according to their profits and try to find a greedy solution.

Approaches (2)
Greedy Solution

The key observation here is that we will always try to maximize our profit by giving priority to the job with maximum profit. Initially, we will sort the jobs according to their profits and then check for each job as to whether it is possible to perform it.

 

The algorithm will be-

  • We will initialize an array/list ‘time’ of length N, with each time[i] denoting whether a job is scheduled at the i-th moment.
  • We will sort the jobs according to their profits.
  • For each job i, we will:
    • We will begin iterating from deadline[i] to 1 and find the maximum time where no job is scheduled by querying the time array.
    • If we get the required moment, ‘optTime’:
      • Set time[optTime] to 1.
      • Increase our final answer by profit[i].
    • Else, we skip the current job.
Time Complexity

O(N^2), where N denotes the total number of jobs to perform.

 

The time complexity due to searching for ‘optTime’ for each job will be O(N). As we are iterating over all the jobs in O(N) time complexity, the overall time complexity will be O(N^2). The complexity due to querying the time array will be O(1) and the time complexity due to sorting will be O(N*log(N)). Hence, the overall Time Complexity is O(N^2). 

Space Complexity

O(N), where N denotes the total number of jobs to perform.

 

The space complexity required for the time array will be O(N). Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Job Scheduling Problem
Full screen
Console