1665. Minimum Initial Energy to Finish Tasks

Time: O(n log n)

Space: O(1)

Intuition

The key insight is that the optimal strategy involves sorting tasks by their net cost (actual - minimum). By processing tasks in this order, you minimize wasted energy. At each task, if your accumulated "savings" don't meet the task's minimum requirement, you must top up the initial energy; otherwise you deduct the actual cost.

Algorithm

1Sort tasks by (actual_effort - minimum_effort) in ascending order.
2Initialise prevSaved = 0 (cumulative energy benefit/cost) and ans = 0 (extra initial energy needed).
3For each sorted task with actual and minimum:
4 If prevSaved < minimum: ans += (minimum - prevSaved), then prevSaved = (minimum - actual).
5 Else: prevSaved -= actual.
6Return ans.

Example Walkthrough

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

1.Sort by (actual - minimum): [1-3=-2, 2-4=-2, 10-11=-1, 8-9=-1, 10-12=-2] → sorted = [[1,3], [2,4], [10,11], [8,9], [10,12]].
2.Process [1,3]: prevSaved=0 < 3 → ans+=3, prevSaved=0. ans=3.
3.Process [2,4]: prevSaved=0 < 4 → ans+=4, prevSaved=2. ans=7.
4.Process [10,11]: prevSaved=2 < 11 → ans+=9, prevSaved=1. ans=16.
5.Process [8,9]: prevSaved=1 < 9 → ans+=8, prevSaved=0. ans=24.
6.Process [10,12]: prevSaved=0 < 12 → ans+=12, prevSaved=2. ans=36.

Output: 36

Common Pitfalls

•The sort key is (actual - minimum), not just maximum. This ordering is critical to optimality.
•prevSaved tracks the net energy state after each task; it can go negative (debt) and be restored by topups.
•When topup is needed, the increase is (minimum - prevSaved), and the new prevSaved becomes (minimum - actual), not just -actual.

1665.cs

// Approach: Sort tasks by (actual - minimum) in ascending order.
// Greedily process sorted tasks tracking prevSaved (cumulative energy saved/spent).
// If prevSaved < minimum required for current task, top up the initial energy.
// Time: O(n log n) Space: O(1)

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

        Array.Sort(tasks, (a, b) => (a[0] - a[1]).CompareTo(b[0] - b[1]));

        foreach (var task in tasks)
        {
            int actual = task[0];
            int minimum = task[1];
            if (prevSaved < minimum)
            {
                ans += minimum - prevSaved;
                prevSaved = minimum - actual;
            }
            else
                prevSaved -= actual;
        }

        return ans;
    }
}

Was this solution helpful?