https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks/ from Akuna Capital

Thinking process:

My first impression for this is that we need to do tasks with bigger minimum value. For example, if we have [[1,2],[1,1]], then it’s obvious we should do [1,2] first.

What if we have two tasks having the same minimum value? like [[1,2],[2,2]]? Now it’s a little bit hard to determine. One technique we can use is to choose an extreme case. For example, our tasks can be [[0,100],[100,100]]. Now it’s obvious that we should go with [0,100] first.

Now we can conclude that we need to do those tasks with bigger minimum-actual first. This is because the bigger minimum-actual, the more energy we save for the next task. So we always want to run those tasks which save us more energy which we can use for later tasks.

Below is the code.

 1class Solution {
 2public:
 3    int N;
 4    int dfs(vector<vector<int>>& t, int i) {
 5        if (i == N-1) {
 6            return t[i][1];
 7        }
 8        return max(dfs(t, i+1) + t[i][0], t[i][1]);
 9    }
10    int minimumEffort(vector<vector<int>>& tasks) {
11        N = tasks.size();
12        sort(tasks.begin(), tasks.end(), [](const vector<int>& a, const vector<int>& b) {
13            return (a[1]-a[0]) > (b[1]-b[0]);
14        });
15        int ans = dfs(tasks, 0);
16        return ans;
17    }
18};