Tasks for Profit Editorial

Practice Problem Link: Tasks For Profit | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a list of tasks, each having a deadline and associated profit if completed within the deadline. Each task takes 1 unit of time to complete. What is the maximum profit you can make?

Naive Approach

A naive solution to this problem is to check all the combinations of the given tasks and find the maximum profit in one of the combinations of the valid tasks. The time complexity for this approach will be exponential.

Analysis

• Time Complexity: O(n*2ⁿ)
• Auxiliary Space Complexity: O(n)

Efficient Approach

The idea is to complete the given tasks in the decreasing order of their profits.

• Initialize a sequence array of size equal to the maximum possible deadline to store the sequence in which the tasks will be completed.
• Start from the task having the highest profit and assign it an unoccupied index in the sequence array while traversing from its deadline to 0 and store the profit in that index.
• Repeat the above step for all tasks in decreasing the order of their profits.
• Traverse the sequence array and add all the profits which will be the answer

Analysis

• Time Complexity: O(n * Maximum Value of Deadline)
• Auxiliary Space Complexity: O(Maximum Value of Deadline)

Implementation

C++

/* This is the Task class definition
class Task {
public:
   int deadline, profit;
   Task(int deadline, int profit) {
       this->deadline = deadline;
       this->profit = profit;
   }
};
*/
bool comp(Task* a, Task* b) {
    return (a->profit > b->profit);
}
int getMaxProfit(vector<Task*> &tasks) {
   sort(tasks.begin(), tasks.end(), comp);
   int n = 0;
   for(int i = 0; i < tasks.size(); i++) {
       n = max(n, tasks[i]->deadline);
   }
   vector<int> sequence (n, 0);
   for (int i = 0; i < tasks.size(); i++) {
       for (int j = tasks[i]->deadline - 1; j >= 0; j--) {
           if (sequence[j] == 0) {
               sequence[j] = tasks[i]->profit;
               break;
           }
       }
   }
   int total_profit = 0;
   for (int i = 0; i < n; i++) {
       total_profit += sequence[i];
   }
   return total_profit;
}

Java

class Solution {
   /* This is the Task class definition
   class Task {
       public int deadline, profit;
       public Task(int deadline, int profit) {
           this.deadline = deadline;
           this.profit = profit;
       }
   }
   */
   class TaskComparator implements Comparator<Task> {
       public int compare(Task t1, Task t2){
           return t2.profit - t1.profit;
       }
   }
   int getMaxProfit(Task[] tasks) {
       Arrays.sort (tasks, new TaskComparator());
       int n = 0;
       for(int i = 0; i < tasks.length; i++) {
           n = Math.max(n, tasks[i].deadline);
       }
       int[] sequence = new int[n];
       for (int i = 0; i < tasks.length; i++) {
           for (int j = tasks[i].deadline - 1; j >= 0; j--) {
               if (sequence[j] == 0) {
                   sequence[j] = tasks[i].profit;
                   break;
               }
           }
       }
       int total_profit = 0;
       for (int i = 0; i < n; i++) {
           total_profit += sequence[i];
       }
       return total_profit;
   }
}

Optimal Approach

This problem can be solved efficiently using a greedy approach.

• Sort the given tasks in increasing order of their deadline.
• Traverse the tasks and add the selected tasks in a min-heap.
  • To select a task, if its deadline is greater than the number of tasks selected till now then simply add it to the min-heap.
  • Otherwise, compare the selected task having the minimum profit and the profit of the current task and choose the one having the greater profit.
• Finally, take the sum of all the profits in the min-heap and return it as the answer.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Task class definition
class Task {
public:
   int deadline, profit;
   Task(int deadline, int profit) {
       this->deadline = deadline;
       this->profit = profit;
   }
};
*/
bool comp(Task* a, Task* b) {
   return (a->deadline < b->deadline);
}
int getMaxProfit(vector<Task*> &tasks) {
   sort(tasks.begin(), tasks.end(), comp);
   priority_queue<int, vector<int>, greater<int>> chosenTasks;
   for (int i = 0; i < tasks.size(); i++) {
       if (chosenTasks.size() == tasks[i]->deadline) {
           if(chosenTasks.top() > tasks[i]->profit) {
               continue;
           }
           chosenTasks.pop();
       }
       chosenTasks.push(tasks[i]->profit);
   }
   int totalProfit = 0;
   while (!chosenTasks.empty()) {
       totalProfit += chosenTasks.top();
       chosenTasks.pop();
   }
   return totalProfit;
}

Java

class Solution {
   /* This is the Task class definition
   class Task {
       public int deadline, profit;
       public Task(int deadline, int profit) {
           this.deadline = deadline;
           this.profit = profit;
       }
   }
   */
   class TaskComparator implements Comparator<Task> {
       public int compare(Task t1, Task t2){
           return t1.deadline - t2.deadline;
       }
   }
   int getMaxProfit(Task[] tasks) {
       Arrays.sort (tasks, new TaskComparator());
       PriorityQueue<Integer> chosenTasks = new PriorityQueue<Integer> ();
       for (int i = 0; i < tasks.length; i++) {
           if (chosenTasks.size() == tasks[i].deadline) {
               if(chosenTasks.peek() > tasks[i].profit) {
                   continue;
               }
               chosenTasks.poll();
           }
           chosenTasks.add(tasks[i].profit);
       }
       int totalProfit = 0;
       while (!chosenTasks.isEmpty()) {
           totalProfit += chosenTasks.peek();
           chosenTasks.poll();
       }
       return totalProfit;
   }
}