Problem

You are given an array tasks where tasks[i] = [actuali, minimumi]:

  • actuali is the actual amount of energy you spend to finish the ith task.
  • minimumi 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 theminimum initial amount of energy you will need to finish all the tasks.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Explanation:
Starting with 8 energy, we finish the tasks in the following order:
    - 3rd task. Now energy = 8 - 4 = 4.
    - 2nd task. Now energy = 4 - 2 = 2.
    - 1st task. Now energy = 2 - 1 = 1.
Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.

Example 2

1
2
3
4
5
6
7
8
9

Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32
Explanation:
Starting with 32 energy, we finish the tasks in the following order:
    - 1st task. Now energy = 32 - 1 = 31.
    - 2nd task. Now energy = 31 - 2 = 29.
    - 3rd task. Now energy = 29 - 10 = 19.
    - 4th task. Now energy = 19 - 10 = 9.
    - 5th task. Now energy = 9 - 8 = 1.

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
Output: 27
Explanation:
Starting with 27 energy, we finish the tasks in the following order:
    - 5th task. Now energy = 27 - 5 = 22.
    - 2nd task. Now energy = 22 - 2 = 20.
    - 3rd task. Now energy = 20 - 3 = 17.
    - 1st task. Now energy = 17 - 1 = 16.
    - 4th task. Now energy = 16 - 4 = 12.
    - 6th task. Now energy = 12 - 6 = 6.

Constraints

  • 1 <= tasks.length <= 10^5
  • 1 <= actual​i <= minimumi <= 10^4

Solution

Method 1 – Greedy Sort by (minimum - actual)

Intuition

To minimize the initial energy, we should do the tasks that require a large gap between minimum and actual energy first. Sorting tasks by (minimum - actual) descending ensures we always have enough energy for the hardest-to-start tasks.

Approach

  1. Sort tasks by (minimum - actual) in descending order.
  2. Initialize total actual energy spent and the required initial energy.
  3. For each task, update the required initial energy to be at least the minimum required for the current task plus the total actual energy spent so far.
  4. After each task, add its actual energy to the total spent.
  5. Return the required initial energy.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int minimumEnergy(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [](auto& a, auto& b) {
            return a[1] - a[0] > b[1] - b[0];
        });
        int ans = 0, sum = 0;
        for (auto& t : tasks) {
            ans = max(ans, t[1] + sum);
            sum += t[0];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import "sort"
func minimumEnergy(tasks [][]int) int {
    sort.Slice(tasks, func(i, j int) bool {
        return tasks[i][1]-tasks[i][0] > tasks[j][1]-tasks[j][0]
    })
    ans, sum := 0, 0
    for _, t := range tasks {
        if t[1]+sum > ans {
            ans = t[1]+sum
        }
        sum += t[0]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int minimumEnergy(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));
        int ans = 0, sum = 0;
        for (int[] t : tasks) {
            ans = Math.max(ans, t[1] + sum);
            sum += t[0];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minimumEnergy(tasks: Array<IntArray>): Int {
        tasks.sortByDescending { it[1] - it[0] }
        var ans = 0
        var sum = 0
        for (t in tasks) {
            ans = maxOf(ans, t[1] + sum)
            sum += t[0]
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

def minimum_energy(tasks: list[list[int]]) -> int:
    tasks.sort(key=lambda x: x[1] - x[0], reverse=True)
    ans = 0
    s = 0
    for a, m in tasks:
        ans = max(ans, m + s)
        s += a
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn minimum_energy(tasks: Vec<Vec<i32>>) -> i32 {
        let mut tasks = tasks;
        tasks.sort_by(|a, b| (b[1] - b[0]).cmp(&(a[1] - a[0])));
        let mut ans = 0;
        let mut sum = 0;
        for t in tasks {
            ans = ans.max(t[1] + sum);
            sum += t[0];
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    minimumEnergy(tasks: number[][]): number {
        tasks.sort((a, b) => (b[1] - b[0]) - (a[1] - a[0]));
        let ans = 0, sum = 0;
        for (const t of tasks) {
            ans = Math.max(ans, t[1] + sum);
            sum += t[0];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of tasks. Sorting dominates.
  • 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.