1665. Minimum Initial Energy to Finish Tasks #

Problem #

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 <= actuali <= minimumi <= 104

Problem Summary #

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

actual i is the actual energy required to complete the i-th task.
minimum i is the minimum energy required before starting the i-th task.

For example, if the task is [10, 12] and your current energy is 11, then you cannot start this task. If your current energy is 13, you can complete this task, and your remaining energy after completing it will be 3. You can complete the tasks in any order. Return the minimum initial energy required to complete all tasks.

Solution Approach #

Given a task array, each element represents a task, and each task has an actual energy consumption value and the minimum energy required to start this task. Output the minimum initial energy needed to complete all tasks.
The intuition for this problem is greedy. First sort the tasks by minimum - actual. Complete the tasks with larger differences first, so the remaining energy can satisfy subsequent tasks as much as possible. This makes it more likely to complete all tasks. When iterating through the task array, store the current energy in cur. If the current energy is not enough to start the next task, then this difference is what needs to be made up, and this energy is part of the minimum initial energy, so add these difference values. If the current energy can start the next task, then update the current energy by subtracting the actual energy consumed, and continue the loop. After the loop ends, the minimum initial energy can be obtained.

Code #

package leetcode

import (
	"sort"
)

func minimumEffort(tasks [][]int) int {
	sort.Sort(Task(tasks))
	res, cur := 0, 0
	for _, t := range tasks {
		if t[1] > cur {
			res += t[1] - cur
			cur = t[1] - t[0]
		} else {
			cur -= t[0]
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Task define
type Task [][]int

func (task Task) Len() int {
	return len(task)
}

func (task Task) Less(i, j int) bool {
	t1, t2 := task[i][1]-task[i][0], task[j][1]-task[j][0]
	if t1 != t2 {
		return t2 < t1
	}
	return task[j][1] < task[i][1]
}

func (task Task) Swap(i, j int) {
	t := task[i]
	task[i] = task[j]
	task[j] = t
}