1665. Minimum Initial Energy to Finish Tasks

題目 / Problem

中文： 給定一個陣列 tasks，其中 tasks[i] = [actualᵢ, minimumᵢ]： - actualᵢ 是完成第 i 個任務實際消耗的能量。 - minimumᵢ 是開始第 i 個任務時你必須擁有的最低能量（注意：只要「擁有」就好，並不會真的扣這麼多，扣的是 actualᵢ）。

例如任務 [10, 12]：若當前能量為 11，因為小於 12，無法開始；若為 13，可以開始，做完後剩 13 - 10 = 3。

你可以任意順序執行所有任務。請回傳「能完成全部任務」所需的最小初始能量。

English: You are given tasks where tasks[i] = [actualᵢ, minimumᵢ]. To start task i your current energy must be ≥ minimumᵢ; completing it subtracts actualᵢ from your energy. You may execute the tasks in any order. Return the minimum initial energy that lets you finish all tasks.

Constraints / 限制： - 1 ≤ tasks.length ≤ 10⁵ - 1 ≤ actualᵢ ≤ minimumᵢ ≤ 10⁴

Worked example / 範例： tasks = [[1,2],[2,4],[4,8]] → output 8 從 8 開始：做 [4,8]（8≥8）→ 剩 4；做 [2,4]（4≥4）→ 剩 2；做 [1,2]（2≥2）→ 剩 1。✓

名詞解釋 / Glossary

• Greedy / 貪心法：每一步只做「當下看起來最好」的選擇，而不是把所有可能順序都列舉出來。本題中「最好的順序」需要一個明確的排序規則。
• Slack (剩餘餘裕) / minimumᵢ − actualᵢ：任務的「門檻」與「實際花費」之差。slack 大代表這個任務「進入門檻很高，但花費不多」，做完後剩很多能量；slack 小代表「進去就幾乎全花光」。
• Exchange argument / 交換論證：證明排序規則正確的標準技巧。假設最佳解中存在兩個相鄰任務違反規則，證明交換它們之後解不變壞，從而得出排序規則必然是最佳的。
• Prefix sum / 前綴和：在從前往後遍歷時，把目前已花費的 actual 累加起來。
• qsort (C 標準函式庫)：C 的排序函式，需要傳入比較函式 int cmp(const void* a, const void* b)，回傳負數表示 a 應排前面，正數表示 b 應排前面。
• Lambda (C++)：匿名函式，寫法 [](T a, T b){ return ...; }，常用來給 std::sort 傳比較規則。
• std::vector<std::vector<int>>：可動態擴張的二維陣列，類似 Python 的 list of lists。
• Range-for / 範圍 for 迴圈：for (auto& t : tasks) 直接遍歷容器中的每個元素，auto& 表示「自動推導型別並取參考避免複製」。

思路

最直觀的想法是試所有排列（n! 種），但 n 可達 10⁵，完全不可行。觀察任務 [actual, minimum]，做完後扣的是 actual，但「進去的門檻」是 minimum。差值 slack = minimum - actual 像是一筆「必須暫時保留、之後又會還給你」的押金。直覺上應該趁手上能量還多的時候，先做押金大（slack 大）的任務；等做完它，能量會回補大部分，再去處理押金小的小任務。這個直覺用交換論證可以嚴格證明：假設相鄰兩個任務 A、B，先做 A 再做 B 所需的最小初始能量為 max(min_A, actual_A + min_B)；先做 B 再做 A 為 max(min_B, actual_B + min_A)。因為 actual ≥ 1，兩個 max 都由「後者」主導，比較 actual_A + min_B 與 actual_B + min_A，化簡得「slack 大的應該排前面」。所以按 minimum − actual 由大到小排序，再從前往後模擬：紀錄目前已累積花掉的 actual（記為 spent），對每個任務更新 ans = max(ans, spent + minimum)，然後 spent += actual。最後 ans 就是答案，因為 ans 必須同時 ≥ 每個任務開始時的門檻 spent_before_it + minimum。

The brute force tries every permutation (n!) which blows up at n = 10⁵, so we need a smarter rule for ordering tasks. Each task [actual, minimum] only spends actual but demands you hold minimum before starting — the gap slack = minimum − actual is like a refundable deposit. The intuition is to front-load tasks with large slack while you still have lots of energy, so that the "deposit" is comfortable; small-slack tasks (cheap deposits) can wait until later. A formal exchange argument confirms this: for two adjacent tasks A and B, doing A first needs initial energy max(min_A, actual_A + min_B) and doing B first needs max(min_B, actual_B + min_A); since actual ≥ 1 both maxes are dominated by the second term, and comparing them simplifies to "the task with the larger min − actual should go first." So sort tasks by minimum − actual in descending order, then sweep left to right while tracking spent (total actual consumed so far). For each task, the energy needed at its starting moment is spent + minimum, so the answer is the maximum of that quantity over all tasks. We never need to actually pick an initial energy and simulate; we just compute the tightest constraint.

逐步走查 / Walkthrough

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

Compute slack = min − actual for each: - [1,2] → slack 1 - [2,4] → slack 2 - [4,8] → slack 4

Sort by slack descending → [[4,8], [2,4], [1,2]].

Sweep, maintaining spent = 0, ans = 0:

Return ans = 8. ✓

Solution — C

// Algorithm / 演算法：
// 按 (minimum - actual) 由大到小排序 (greedy / exchange-argument optimal)，
// 然後掃過一次，記錄已花費 actual 之和 spent，答案 = max(spent + minimum)。
// Sort tasks by (min - actual) descending, then sweep tracking spent;
// the answer is the max of (spent_before_task + minimum) over all tasks.

#include <stdlib.h>   // 為了 qsort / for qsort

// 比較函式：a, b 都是 int*（指向 tasks[i] 那一列的指標）
// Comparator: a and b are int** pointing to a row of tasks.
// qsort 傳給我們的是「指向元素的指標」，而元素本身是 int*，所以 a 實際型別是 int**。
// qsort hands us pointers to elements; each element is an int*, so a is int**.
static int cmp(const void *a, const void *b) {
    // 解兩層指標拿到 row（int*）/ dereference once to get the row (int*)
    const int *ra = *(const int *const *)a;
    const int *rb = *(const int *const *)b;
    // slack_a = ra[1] - ra[0]；slack_b = rb[1] - rb[0]
    // 我們要 slack 大的排前面，所以回傳 slack_b - slack_a
    // We want larger slack first, so return slack_b - slack_a.
    int slack_a = ra[1] - ra[0];
    int slack_b = rb[1] - rb[0];
    return slack_b - slack_a;   // 負數代表 a 排前面 / negative means a comes first
}

// LeetCode signature：tasks 是 int**（指標的陣列，每個指向長度 2 的 int 陣列）
// LeetCode signature: tasks is int** (array of pointers, each row has length 2).
int minimumEffort(int** tasks, int tasksSize, int* tasksColSize) {
    // 原地排序 tasks（修改傳入的陣列順序）
    // Sort tasks in-place; we don't need the original order afterwards.
    qsort(tasks, tasksSize, sizeof(int *), cmp);

    long spent = 0;   // 已累計花費的 actual / running sum of actual costs
    long ans = 0;     // 目前答案下界 / current lower bound for initial energy
    // 用 long 避免極端情況下 10^5 * 10^4 = 10^9 接近 int 上限 (~2.1e9)
    // long avoids overflow risk when spent + minimum could approach 2 * 10^9.

    for (int i = 0; i < tasksSize; i++) {
        int actual  = tasks[i][0];   // 實際花費 / energy actually spent
        int minimum = tasks[i][1];   // 進入門檻 / threshold required to start
        // 開始這個任務前需要 spent + minimum 的初始能量
        // To start this task we need initial energy of at least spent + minimum.
        long need = spent + minimum;
        if (need > ans) ans = need;  // 取最大值 / take the max constraint
        spent += actual;             // 做完後累加實際花費 / accumulate actual after finishing
    }
    return (int)ans;   // 題目保證落在 int 範圍內 / answer fits in int
}

Solution — C++

// Algorithm / 演算法：
// 與 C 版本完全相同：按 (minimum - actual) 由大到小排序後掃描，
// 取 max(spent + minimum) 作為答案。這裡用 std::sort + lambda 表達。
// Same idea as the C version: sort by (min - actual) descending and sweep,
// taking the max of (spent + minimum). Implemented with std::sort + a lambda.

#include <vector>
#include <algorithm>   // std::sort, std::max

class Solution {
public:
    int minimumEffort(std::vector<std::vector<int>>& tasks) {
        // std::sort + lambda 比較函式
        // a, b 都是 const vector<int>& （tasks 的一列）
        // The lambda is a comparator: return true when a should come before b.
        // 我們要 slack 大的在前 / we want larger slack first.
        std::sort(tasks.begin(), tasks.end(),
                  [](const std::vector<int>& a, const std::vector<int>& b) {
                      // a[1]-a[0] 是 a 的 slack；b[1]-b[0] 是 b 的 slack
                      // Return true ⇒ a comes before b.
                      return (a[1] - a[0]) > (b[1] - b[0]);
                  });

        long spent = 0;   // 已花費的 actual 累計 / running total of actual costs
        long ans   = 0;   // 答案下界 / current best lower bound on initial energy

        // range-for：逐一取得每個任務的 reference (auto& 避免複製)
        // range-for loop: iterate by reference to avoid copying each vector.
        for (const auto& t : tasks) {
            int actual  = t[0];                 // 本任務實際花費 / actual spend
            int minimum = t[1];                 // 本任務開始門檻 / minimum to start
            ans = std::max(ans, spent + minimum); // 更新答案 / tighten lower bound
            spent += actual;                    // 累加花費 / accumulate after finishing
        }
        return static_cast<int>(ans);   // 轉回 int 回傳 / cast back to int
    }
};

複雜度 / Complexity

• Time: O(n log n) — 排序佔主導 (std::sort / qsort)，掃描只是 O(n)。n 是 tasks.length，最多 10⁵，log n ≈ 17，非常快。 Sorting dominates; the linear sweep is O(n). Here n is the number of tasks (≤ 10⁵), so n log n ≈ 1.7 × 10⁶ operations.
• Space: O(1) 額外空間（不算輸入；qsort / std::sort 通常是 O(log n) 遞迴堆疊，常被視為 O(1) auxiliary）。 Auxiliary space is O(1) ignoring the recursion stack used by the sort itself (O(log n) in practice).

Pitfalls & Edge Cases

• 排序方向反了 / Sorting the wrong way：寫成「slack 小的在前」會得到錯誤答案。記得是 slack 由大到小（larger-slack-first）— greedy 反過來就破功。
• 以 minimum 或 actual 單獨排序 / Sorting by minimum or actual alone：這兩者都不是最佳排序鍵；只有差值 minimum − actual 才滿足交換論證。
• 誤以為要實際模擬「我目前有多少能量」：不需要。我們是反過來算「最少要多少才夠」，直接掃過去取 max(spent + minimum) 即可。You don't track a running energy from some chosen start value — you compute the tightest constraint instead.
• 整數溢位 / Integer overflow：spent + minimum 最大約為 10⁵ × 10⁴ + 10⁴ ≈ 10⁹，仍在 32-bit int 範圍內 (~2.1 × 10⁹)，但保留 long 是更安全的寫法，避免比較邏輯出錯時悄悄溢位。
• 比較函式回傳值必須是「順序」而非 bool（C 版本）：C 的 qsort 比較函式回傳 int（負/零/正），不是 bool；寫成 return slack_a > slack_b; 是錯的（會得到非穩定且錯誤的排序）。
• tasksColSize 在 C 版本沒用到：題目保證每列都是長度 2，安全忽略；但若題目改成可變列長，就要注意。
• 空輸入 / Empty input：題目保證 tasks.length ≥ 1，但程式碼自然處理（迴圈不執行，回傳 0）—— 不需特判。
• 相同 slack 的 tie-break：當兩個任務 slack 相同時，順序不影響答案（兩種順序給出相同的最大值），所以排序穩定性無關緊要。