CSES Solutions - Tasks and Deadlines

You have to process N tasks. Each task has a duration and a deadline given as 2D array tasks[][] such that for task i, tasks[i][0] is the duration, and tasks[i][1] is the deadline. You will process the tasks in some order one after another. Your reward for a task is d-f where d is its deadline and f is your finishing time. (The starting time is 0, and you have to process all tasks even if a task would yield a negative reward.)

What is your maximum reward if you act optimally?

Examples:

Input: N = 3, tasks[][] = {{6, 10}, {8, 15}, {5, 12}}
Output: 2
Explanation:

• Perform task 3 in time [0, 5]. Reward = 12 - 5 = 7.
• Perform task 1 in time [5, 11]. Reward = 10 - 11 = -1.
• Perform task 2 in time [11, 19]. Reward = 19 - 15 = -4

Maximum reward = 7 - 1 - 4 = 2.

Input: N = 4, tasks[][] = {{1, 1}, {1, 2}, {1, 3}, {1, 4}}
Output: 0
Explanation:

• Perform task 1 in time [0, 1]. Reward = 1 - 1 = 0.
• Perform task 2 in time [1, 2]. Reward = 2 - 2 = 0.
• Perform task 3 in time [2, 3]. Reward = 3 - 3 = 0.
• Perform task 4 in time [3, 4]. Reward = 4 - 4 = 0.

Maximum reward = 0

Approach: To solve the problem, follow the below idea:

Let's first solve the problem for two tasks and then we can extend it to all the tasks. Assume we have two tasks T1 and T2:

• If we perform T1 before T2, reward = (deadline(T1) - duration(T1)) + (deadline(T2) - duration(T1) - duration(T2)). So, reward1 = deadline(T1) + deadline(T2) - 2 * duration(T1) - duration(T2)
• If we perform T2 before T1, reward = (deadline(T2) - duration(T2)) + (deadline(T1) - duration(T2) - duration(T1)). So, reward2 = deadline(T1) + deadline(T2) - 2 * duration(T2) - duration(T1)

From the above two formulas, we can say that the rewards will only differ according to the values of duration(T1) and duration(T2) and are independent of whether deadline(T1) is greater or deadline(T2). Since the duration of the task performed earlier is subtracted more times (twice) as compared to the duration of task performed later, we can conclude that the tasks with smaller duration should be performed first.

The problem can be solved using Greedy approach. We can perform the tasks in increasing order of their durations. We also need to keep track of the current time and then for each task, we need to add the difference: task deadline - task completion time. Sum of all these differences is the final answer.

Step-by-step algorithm:

• Sort the tasks in ascending order of the durations.
• Maintain a variable, say currentTime to keep track of the time elapsed so far and another variable, say totalReward to store the total sum of rewards.
• Iterate over all the tasks and keep track of the time elapsed.
  • After completing ith task, add the reward (deadline - currentTime) to totalReward.
• After iterating over all the tasks, return totalReward as the final answer.

Below is the implementation of the algorithm:

#include <bits/stdc++.h> #define ll long long int using namespace std; // function to calculate the total rewards ll solve(vector<vector<ll> >& tasks, ll N) {  // Sort the tasks in ascending order of their durations  sort(tasks.begin(), tasks.end());  // Variable to keep track of the time elapsed so far  ll currentTime = 0;  // Variable to store the total sum of rewards  ll totalReward = 0;  // Iterate over all the tasks and calculate the total  // reward  for (int i = 0; i < N; i++) {  currentTime += tasks[i][0];  totalReward += (tasks[i][1] - currentTime);  }  return totalReward; } int main() {  // Sample Input  ll N = 3;  vector<vector<ll> > tasks  = { { 6, 10 }, { 8, 15 }, { 5, 12 } };  cout << solve(tasks, N);  // your code goes here  return 0; } 

import java.util.Arrays; import java.util.Comparator; import java.util.Vector; class Main {  // Function to calculate the total rewards  static long solve(Vector<Vector<Long>> tasks, long N) {  // Sort the tasks in ascending order of their durations  tasks.sort(Comparator.comparingLong(o -> o.get(0)));  // Variable to keep track of the time elapsed so far  long currentTime = 0;  // Variable to store the total sum of rewards  long totalReward = 0;  // Iterate over all the tasks and calculate the total reward  for (int i = 0; i < N; i++) {  currentTime += tasks.get(i).get(0);  totalReward += (tasks.get(i).get(1) - currentTime);  }  return totalReward;  }  // Driver code  public static void main(String[] args) {  // Sample Input  long N = 3;  Vector<Vector<Long>> tasks = new Vector<>(Arrays.asList(  new Vector<>(Arrays.asList(6L, 10L)),  new Vector<>(Arrays.asList(8L, 15L)),  new Vector<>(Arrays.asList(5L, 12L))  ));  System.out.println(solve(tasks, N));  } } // This code is contributed by shivamgupta0987654321 

// Function to calculate the total rewards function solve(tasks) {  // Sort the tasks in ascending order of their durations  tasks.sort((a, b) => a[0] - b[0]);  // Variables to keep track of the time elapsed so far and the total sum of rewards  let currentTime = 0;  let totalReward = 0;  // Iterate over all the tasks and calculate the total reward  for (let i = 0; i < tasks.length; i++) {  currentTime += tasks[i][0];  totalReward += tasks[i][1] - currentTime;  }  return totalReward; } // Main function function main() {  // Sample Input  const tasks = [  [6, 10],  [8, 15],  [5, 12]  ];  console.log(solve(tasks)); } // Call the main function main(); 

# Function to calculate the total rewards def solve(tasks): # Sort the tasks in ascending order of their durations tasks.sort() # Variable to keep track of the time elapsed so far current_time = 0 # Variable to store the total sum of rewards total_reward = 0 # Iterate over all the tasks and calculate the total reward for duration, reward in tasks: current_time += duration total_reward += (reward - current_time) return total_reward if __name__ == "__main__": # Sample Input tasks = [[6, 10], [8, 15], [5, 12]] print(solve(tasks)) 

2

Time Complexity: O(N * logN), where N is the number of tasks to be processed.
Auxiliary Space: O(N)