Last Updated: 26 Apr, 2021

Optimal Ordering Of Tasks

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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 :

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]’

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

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

The steps are as follows:

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

Solve now