Problem Statement in English

You’re given a 2D array tasks where tasks[i] = [actuali, minimumi] indicates that the i-th task requires at least minimumi energy to start and consumes actuali energy to finish. You can finish the tasks in any order you like.

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

Approach

We’re going to start with the assumption that we need 0 energy to start. As and when we see deficiencies, we’ll add the extra energy needed to the total and also to the current energy. After that we’ll reduce the current energy by the actual energy consumed by the task.

So that brings us to the question of in which order should we do the tasks. We should do the tasks with the highest difference between minimum and actual energy first.

This is because according to the constraints is always actual[i] <= minimum[i], and if we do the tasks with bigger difference first, we might end up with a surplus which we can then allocate to subsequent tasks, thus allowing to reduce the extra energy needed. It definitely does feel a bit counterintuitive at first.

And we’re done!

Solution in Python


class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1] - x[0], reverse=True)
        
        current_energy = 0
        total_needed = 0
        
        for actual, minimum in tasks:
            if current_energy < minimum:
                extra = minimum - current_energy
                total_needed += extra
                current_energy += extra
            
            current_energy -= actual
            
        return total_needed

Complexity

  • Time: $O(n \log n)$
    Since we sort the tasks based on the difference between minimum and actual energy.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space.

Mistakes I Made

I couldn’t figure out the sort order :(

And we are done.