1665. Minimum Initial Energy to Finish Tasks LeetCode Solution

In this guide, you will get 1665. Minimum Initial Energy to Finish Tasks LeetCode Solution with the best time and space complexity. The solution to Minimum Initial Energy to Finish Tasks problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Initial Energy to Finish Tasks solution in C++
4. Minimum Initial Energy to Finish Tasks solution in Java
5. Minimum Initial Energy to Finish Tasks solution in Python
6. Additional Resources

Problem Statement of Minimum Initial Energy to Finish Tasks

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 the minimum initial amount of energy you will need to finish all the tasks.

Example 1:

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:

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:

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 <= 105
1 <= actual​i <= minimumi <= 104

Complexity Analysis

• Time Complexity: O(\texttt{sort})
• Space Complexity: O(\texttt{sort})

1665. Minimum Initial Energy to Finish Tasks LeetCode Solution in C++

class Solution {
 public:
  int minimumEffort(vector<vector<int>>& tasks) {
    int ans = 0;
    int prevSaved = 0;

    ranges::sort(tasks, ranges::greater{},
                 [](const vector<int>& task) { return task[1] - task[0]; });

    for (const vector<int>& task : tasks) {
      const int actual = task[0];
      const int minimum = task[1];
      if (prevSaved < minimum) {
        ans += minimum - prevSaved;
        prevSaved = minimum - actual;
      } else {
        prevSaved -= actual;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1665. Minimum Initial Energy to Finish Tasks LeetCode Solution in Java

class Solution {
  public int minimumEffort(int[][] tasks) {
    int ans = 0;
    int prevSaved = 0;

    Arrays.sort(tasks, (a, b) -> Integer.compare(b[1] - b[0], a[1] - a[0]));

    for (int[] task : tasks) {
      final int actual = task[0];
      final int minimum = task[1];
      if (prevSaved < minimum) {
        ans += minimum - prevSaved;
        prevSaved = minimum - actual;
      } else {
        prevSaved -= actual;
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

1665. Minimum Initial Energy to Finish Tasks LeetCode Solution in Python

class Solution:
  def minimumEffort(self, tasks: list[list[int]]) -> int:
    ans = 0
    prevSaved = 0

    for actual, minimum in sorted(tasks, key=lambda x: x[0] - x[1]):
      if prevSaved < minimum:
        ans += minimum - prevSaved
        prevSaved = minimum - actual
      else:
        prevSaved -= actual

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.