Skip to content

1665. Minimum Initial Energy to Finish Tasks 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int minimumEffort(vector<vector<int>>& tasks) {
    int ans = 0;
    int prevSaved = 0;

    ranges::sort(tasks, [](const vector<int>& a, const vector<int>& b) {
      return a[1] - a[0] > b[1] - b[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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int minimumEffort(int[][] tasks) {
    int ans = 0;
    int prevSaved = 0;

    Arrays.sort(tasks, (a, b) -> (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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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