Skip to content

1665. Minimum Initial Energy to Finish Tasks

Description

You are given an array tasks where tasks[i] = [actuali, minimumi]:

  • actuali is the actual amount of energy you spend to finish the ith task.
  • minimumi is the minimum amount of energy you require to begin the ith task.

For example, if the task is [10, 12] and your current energy is 11, you cannot start this task. However, if your current energy is 13, you can complete this task, and your energy will be 3 after finishing it.

You can finish the tasks in any order you like.

Return the minimum initial amount of energy you will need to finish all the tasks.

 

Example 1:

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Explanation:
Starting with 8 energy, we finish the tasks in the following order:
    - 3rd task. Now energy = 8 - 4 = 4.
    - 2nd task. Now energy = 4 - 2 = 2.
    - 1st task. Now energy = 2 - 1 = 1.
Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.

Example 2:

Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32
Explanation:
Starting with 32 energy, we finish the tasks in the following order:
    - 1st task. Now energy = 32 - 1 = 31.
    - 2nd task. Now energy = 31 - 2 = 29.
    - 3rd task. Now energy = 29 - 10 = 19.
    - 4th task. Now energy = 19 - 10 = 9.
    - 5th task. Now energy = 9 - 8 = 1.

Example 3:

Input: tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
Output: 27
Explanation:
Starting with 27 energy, we finish the tasks in the following order:
    - 5th task. Now energy = 27 - 5 = 22.
    - 2nd task. Now energy = 22 - 2 = 20.
    - 3rd task. Now energy = 20 - 3 = 17.
    - 1st task. Now energy = 17 - 1 = 16.
    - 4th task. Now energy = 16 - 4 = 12.
    - 6th task. Now energy = 12 - 6 = 6.

 

Constraints:

  • 1 <= tasks.length <= 105
  • 1 <= actual​i <= minimumi <= 104

Solutions

Solution 1: Greedy + Custom Sorting

Assume the number of tasks is \(n\) and the initial energy level is \(E\). Consider completing the last task. This requires that after completing the first \(n-1\) tasks, the remaining energy level is not less than the energy level required to complete the last task \(m_n\), i.e.,

\[ E-\sum_{i=1}^{n-1} a_i \geq m_n \]

We can express \(m_n\) as \(a_n+(m_n - a_n)\), and then transform the above formula to get:

\[ E-\sum_{i=1}^{n-1} a_i \geq a_n+(m_n - a_n) \]

Rearranging, we get:

\[ E \geq \sum_{i=1}^{n} a_i + (m_n - a_n) \]

Where \(\sum_{i=1}^{n} a_i\) is fixed. To minimize the initial energy level \(E\), we need to minimize \(m_n - a_n\), i.e., maximize \(a_n-m_n\).

Therefore, we can sort the tasks in ascending order of \(a_i-m_i\). Then we traverse the tasks from front to back. For each task, if the current energy level \(cur\) is less than \(m_i\), we need to increase the energy level by \(m_i - cur\) to make the current energy level exactly equal to \(m_i\). Then we complete the task and update \(cur = cur - a_i\). Continue traversing until all tasks are completed, and we can get the minimum initial energy level required.

The time complexity is \(O(n\times \log n)\), where \(n\) is the number of tasks. Ignoring the space overhead of sorting, the space complexity is \(O(1)\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> a[0] - b[0] - (a[1] - b[1]));
        int ans = 0, cur = 0;
        for (var task : tasks) {
            int a = task[0], m = task[1];
            if (cur < m) {
                ans += m - cur;
                cur = m;
            }
            cur -= a;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 (auto& task : tasks) {
            int a = task[0], m = task[1];
            if (cur < m) {
                ans += m - cur;
                cur = m;
            }
            cur -= a;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func minimumEffort(tasks [][]int) (ans int) {
    sort.Slice(tasks, func(i, j int) bool { return tasks[i][0]-tasks[i][1] < tasks[j][0]-tasks[j][1] })
    cur := 0
    for _, task := range tasks {
        a, m := task[0], task[1]
        if cur < m {
            ans += m - cur
            cur = m
        }
        cur -= a
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function minimumEffort(tasks: number[][]): number {
    tasks.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));
    let ans = 0;
    let cur = 0;
    for (const [a, m] of tasks) {
        if (cur < m) {
            ans += m - cur;
            cur = m;
        }
        cur -= a;
    }
    return ans;
}

Comments