Optimal Ordering Of Tasks

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in companies
AmazonalibabaIon Group

Problem statement

You are given ‘N’ tasks. Each task has its own duration and deadline stored in array/list 'ARR'. You have to do all the tasks. Reward earned by doing a task is ‘deadline of the task’ - ‘time when the task is done’.

You have to order the tasks in such a way that the sum of rewards is maximized and find the maximum sum of the reward.

Note :

1. The time starts from zero. 
2. Before completing one task another task can not be started. 
3. The reward for doing a task can be negative.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes the number of tasks.

The next ‘N’ lines contain the two space-separated integers “ARR[i][0]” and “ARR[i][1]”, where “ARR[i][0]” is the duration of the ‘i-th’ task and “ARR[i][1]” is the deadline of the ‘i-th’ task.
Output Format : 
For each test case, print the maximum reward for doing all the tasks.

Output for every test case will be printed in a separate line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 10
1 <= N <= 100000
1 <= ARR[ i ][ 0 ] and ARR[ i ][ 1 ] <= 10^5

Where ‘T’ is the number of test cases, 'N' is the number of tasks,  ‘ARR[ i ][ 0 ]’ is the duration and  ‘ARR[ i ][ 1 ]’ deadline of the ‘i-th’ task. 

Time limit: 1 sec
Sample Input 1 :
2
2
1 10
10 1
4
1 1
1 2   
1 4
1 3
Sample Output 1 :
-1
0
Explanation of sample input 1:
In the first test case:
Time starts from zero. 
First, we will do 1’st task. It will be done at time = 1, reward = 10 - 1 = 9.
After first we will do the second task. It will be done at time = 11, reward = 1 - 11 = -10.
Total reward =  9 + ( -10 ) = -1.

In the second test case:
Time starts from zero. 
We will do the task in order  : 3, 4, 2, 1
After time = 1 unit, 3rd task will be done, reward = 4 - 1 = 3.
After time = 2 unit, 4th task will be done, reward = 3 - 2 = 1.
After time = 3 unit, 2nd task will be done, reward = 2 - 3 = - 1.
After time = 4 unit, 1st task will be done, reward = 1 - 4 = - 3.
Total reward = 3 + 1 - 1 - 3 = 0.
Sample Input 2:
2
5
123 250
3 120
67 100
88 93
5 10
1
100 101
Sample Output 2:
38
1
Hint

If there are two tasks ‘i-th’ and ‘(i+1)-th’ when is it optimal to swap them?

Approaches (1)
Sorting

If there are two tasks ‘i-th’ and ‘i + 1-th’ and the duration of ‘i+1-th’ task is smaller than ‘i-th’ task then it is always optimal to swap two tasks. 

 

Proof :

  1. Without swap the total reward of doing ‘i-th’ and ‘i+1-th’ will be.
    1. ‘reward1’ =’deadline[i]’ - ‘duration[i]’ + ‘deadline [i + 1]’ - (‘duration[i]’ + ‘duration[i + 1]’)
    2. ‘reward1’ = ‘deadline[i]’ + ‘deadline[i + 1]’ - 2 * ‘duration[i]’ - ‘duration[i + 1]’

  

  1. Similarly, after the swap total reward will be
    1. ‘reward2’ = ‘deadline[i]’ + ‘deadline[i + 1]’ - 2 * ‘duration[i + 1]’ - ‘duration[i]’
  2. ‘reward2’ - ‘reward1’ =  ‘duration[i]’ - ‘duration[i + 1]’ > 0

So, tasks sorted by their duration will always be optimal. 

 

The steps are as follows:

 

  1. Create a variable ‘ans’ to store the final answer.
  2. Create a variable ‘time’ initialized to 0 to store the current time.
  3. Sort all the tasks by their duration.
  4. Iterate from 0 to ‘N’-1. (say, iterator = 'i')
    1. ‘time’ += ‘arr[i][0]’
    2. ‘ans’ += ‘arr[i][1]’ - ‘time’
  5. Return ‘ans’.

 

Time Complexity

O(N * log(N)), where ‘N’ is the total number of tasks.

 

We will sort all the tasks by their duration, and then iterate through the sorted array. So, the overall time complexity will be O(N * log(N)). 

Space Complexity

O(1). 

 

Constant space required.

Code Solution
(100% EXP penalty)
Optimal Ordering Of Tasks
Full screen
Console