Notebook

1665. Minimum Initial Energy to Finish Tasks

Learn how a greedy sorting strategy based on task 'buffer' minimizes the initial energy needed to complete all tasks in any order.

2 min read GreedySorting

Problem Statement

You are given an array tasks where tasks[i] = [actual_i, minimum_i]:

  • actual_i is the actual amount of energy you spend to finish the ith task.
  • minimum_i is the minimum amount of energy you require to begin the ith task.

For example, if the task is [10, 12] and your current energy is 11, you cannot start this task. However, if your current energy is 13, you can complete this task, and your energy will be 3 after finishing it.

You can finish the tasks in any order you like.

Return the minimum initial amount of energy you will need to finish all the tasks.

Examples

Example 1

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8

Explanation: Starting with 8 energy, finish tasks in this order:

  • 3rd task. Energy = 8 - 4 = 4.
  • 2nd task. Energy = 4 - 2 = 2.
  • 1st task. Energy = 2 - 1 = 1.

Starting with 7 energy does not work because we cannot begin the 3rd task.

Example 2

Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32

Example 3

Input: tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
Output: 27

Constraints

  • 1 <= tasks.length <= 10^5
  • 1 <= actual_i <= minimum_i <= 10^4

Explanation

Think of actual and minimum as two separate dimensions for each task.

The difference minimum - actual is basically how much extra energy you need just to start the task — sort of the “entry cost” on top of what you actually burn. So the idea is to start with the tasks that have the smallest entry cost and leave the ones with the bigger entry cost for later.

Why? Consider two tasks A and B. If we do A then B, we need initial energy ≥ max(minimum_A, actual_A + minimum_B). If we do B then A, we need ≥ max(minimum_B, actual_B + minimum_A). Doing A before B is better when minimum_A - actual_A ≤ minimum_B - actual_B, i.e., when A has a smaller buffer.

Once you sort by that difference, the answer builds up naturally: you need at least minimum of the first task to start, and for each next task you either already have enough carry-over energy or you need to top up to that task’s minimum.

Code

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [&](auto &a, auto &b) {
            return (a[1] - a[0]) < (b[1] - b[0]);
        });
        int ans = tasks[0][1], n = tasks.size();
        for (int i = 1; i < n; i++) {
            ans = max(ans + tasks[i][0], tasks[i][1]);
        }
        return ans;
    }
};

Resources