Job Scheduling

Easy
0/40
1 upvote
Asked in companies
PayPalTekion Corp

Problem statement

You are given a list of ‘N’ jobs which are to be performed. Each job can be characterized by three parameters-

• Start Time, denoting the start time of the job.
• End Time, denoting the end time of the job.
• Profit associated with the job.

You are required to schedule the jobs in such a way that total profit will be maximized.

Note: 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’-
• Start time, End time and profit associated with job ‘A’ being 1, 1 and 30.
• Start time, End time and profit associated with job ‘B’ being 1, 2 and 40.
• Start time, End time and profit associated with job ‘C’ being 3, 4 and 30.

We will perform job ‘B’ at time t = 1 and job ‘C’ at time t = 3. 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 jobes

The next ‘N’ lines contain three space separated integers, start[i], end[i] and profit[i] denoting the start time, end time 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 <= start[i] <= 10^5
1 <= end[i] <=10^5
start[i] <= end[i] 
1 <= profit[i] <= 10^5

Time Limit: 1sec
Sample Input 1 :
2
3
1 2 10
2 3 50
3 4 30
3
1 2 20
3 4 30
5 6 40
Sample Output 1:
50
90

Explanation for Sample 1:

The optimal job scheduling for the first test case will be-
• Job 2 at time t = 2

The total profit in this case will be 50.

The optimal job scheduling for the second test case will be-
• Job 1 at time t = 1
• Job 2 at time t = 3
• Job 3 at time t = 5
The total profit in this case will be 20 + 40 + 30 = 90.
Sample Input 2 :
1
5
1 2 100
1 1 19
1 2 27
1 1 25
1 3 15
Sample Output 2 :
100
Hint

Can we use dynamic programming to solve the above problem?

Approaches (1)
Dynamic Programming

We can also use dynamic programming to solve this problem. We will sort all the jobs according to their finish times. We will then use an iterative dp approach to find the maximum profit.

The algorithm will be-

  • We will sort the jobs according to their finish times.
  • We will keep an array/list ‘dp’ with each dp[i] storing the maximum profit ending at index i.
  • We will run a loop starting from the job which has the least finish time. Let the current job be ‘currJob’.
  • For each iteration-
    • We do not include the currJob in our answer i.e we do dp[i] = dp[i - 1].
    • We now do the following:
      • We find the latest job which has finishing time, less than the ‘currJob’. Let that job be ‘optJob’.
      • We update dp[i] as max(dp[i], dp[optJob] + profit[i]).
  • We finally return the value of dp[N] which will be our answer.
Time Complexity

O(N^2), where N is the number of jobs.

 

The time complexity due to the iteration will be O(N). For each current job, we are finding out the next job which has finishing time, less than the starting time of the current job in O(N) time complexity. Hence overall time complexity will be O(N^2).

Space Complexity

O(N), where N is the number of jobs.

The space complexity due to array/list dp will be O(N).

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