Minimum Initial Energy To Finish Tasks - Leetcode Solution

Problem Statement:

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.

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.

Solution:

The problem can be solved using binary search. We need to find the minimum initial energy to finish all tasks. We can assume the range of energy from 1 to 10^9, as this is the maximum value for the energy.

Steps:

1. We need to calculate the difference between the actual energy and minimum energy for each task.
2. Sort the task based on their difference between actual energy and minimum energy in ascending order.
3. Set the initial energy to 1 and the end energy to 10^9.
4. While the initial energy is less than or equal to the end energy, we will calculate the middle energy.
5. Try to finish all tasks with the middle energy. If we can finish all tasks, then we can reduce the end energy to the middle energy. Otherwise, we can increase the initial energy to the middle energy plus one.
6. After the binary search loop, we will return the initial energy as it will have the minimum value of energy required to finish all tasks.

Code:

Here is the implementation of the above algorithm in Python:

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1] - x[0])
        initial_energy, end_energy = 1, 10 ** 9
        while initial_energy <= end_energy:
            middle_energy = (initial_energy + end_energy) // 2
            energy_left = middle_energy
            finish_all = True
            for task in tasks:
                energy_left -= task[1]
                if energy_left < 0:
                    finish_all = False
                    break
                energy_left += task[0]
            if finish_all:
                end_energy = middle_energy - 1
            else:
                initial_energy = middle_energy + 1
        return initial_energy

Complexity:

The time complexity of the binary search algorithm is O (N log N), where N is the number of tasks. The space complexity is O (1).

1