Solution Explanation: Minimum Initial Energy to Finish Tasks

This problem asks for the minimum initial energy needed to complete a series of tasks, where each task has an energy cost and a minimum energy requirement to start. The key insight is that the order in which we complete the tasks matters. A greedy approach, combined with a specific sorting strategy, provides an efficient solution.

Approach: Greedy with Custom Sorting

1. Sorting: We sort the tasks based on a custom comparator: a[0] - a[1]. This represents the difference between the energy cost (a[0]) and the minimum energy requirement (a[1]). Sorting in ascending order of this difference means we prioritize tasks where the difference is smaller—tasks that are relatively less expensive compared to their minimum requirement. Intuitively, completing such tasks early helps to maintain a higher energy level, reducing the need for a large initial energy boost.

2. Greedy Iteration: We iterate through the sorted tasks. For each task:

   • Energy Check: We check if our current energy level (cur) is sufficient to start the task (cur >= m[1]).
   • Energy Boost: If not enough energy, we need to increase the initial energy (ans) to reach the required level (m[1]). The amount needed is m[1] - cur. We update cur to reflect this energy boost.
   • Task Completion: We subtract the energy cost (a[0]) from the current energy level (cur).

3. Return Value: After completing all tasks, the value of ans represents the minimum initial energy required.

Time and Space Complexity

• Time Complexity: O(n log n), dominated by the sorting step.
• Space Complexity: O(1), We use only a few variables to track the energy levels. The in-place sorting in most implementations also contributes to this constant space.

Code Implementation (Python)

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        ans = cur = 0
        for a, m in sorted(tasks, key=lambda x: x[0] - x[1]):
            if cur < m:
                ans += m - cur
                cur = m
            cur -= a
        return ans
 

The code directly implements the described approach. The sorted() function with the lambda expression performs the custom sorting. The loop iterates through the sorted tasks, managing the energy levels according to the greedy strategy.

Code Implementations (Other Languages)

The core logic remains consistent across different programming languages. Here are examples in Java and C++:

Java:

import java.util.Arrays;
import java.util.Comparator;
 
class Solution {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, Comparator.comparingInt(a -> a[0] - a[1]));
        int ans = 0, cur = 0;
        for (int[] task : tasks) {
            int a = task[0], m = task[1];
            if (cur < m) {
                ans += m - cur;
                cur = m;
            }
            cur -= a;
        }
        return ans;
    }
}

C++:

#include <vector>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [](const auto& a, const auto& b) {
            return a[0] - a[1] < b[0] - b[1];
        });
        int ans = 0, cur = 0;
        for (const auto& task : tasks) {
            int a = task[0], m = task[1];
            if (cur < m) {
                ans += m - cur;
                cur = m;
            }
            cur -= a;
        }
        return ans;
    }
};

These implementations use similar data structures and logic to achieve the same result with efficient time complexity. The choice of language is largely a matter of preference and project requirements.