Minimum Initial Energy to Finish Tasks — Algorithms&Visualizations

Introduction
Recently I’ve got to spend some hours thinking of a useful visualization for a problem whose key point is a pretty straightforward intuition. I am a stronger believer in visualization to help make a concept stick. That being said, I have got to be honest, am not sure if I pulled it off this time, but eventually came up with something that I liked. Let me know your thoughts.

The Problem
Let’s start with the description of this problem which has been labeled as hard by LeetCode. The title is “Minimum Initial Energy to Finish Tasks”:

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.

For some of you, the solution to this problem might be rather easy, and the key point clear. Nevertheless, people think differently from one other, and what it’s easy and immediate for one, might be hard to grasp for some other.
Instead of airing out the key point that solves the problem, I’d rather go through a graphical analysis that is meant to lead everyone to the solution.

First Approach

Let’s see the first given example:

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8

When I drew this picture, my first thought was to sort the tasks by their “minimum” (the second element of the pair representing a task) in ascending order, and the job was done.
Yes, I know, this approach was not generic at all. Drawing conclusions from one single example is not the best of the ideas. As a matter of fact, it was wrong. It’s clear from the second example:
Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32

Second Approach

Applying the strategy of getting started from the task with the biggest “minimum” value to the second example, produces an incorrect result.

The output is supposed to be 32, and we came up with 33.

Where are we making a mistake?
In my opinion, one of the best ways to figure out the issue and move on towards the correct solution is by comparison.
In other words, what I mean to do is picking the correct solution, visualize it, and trying to understand what’s wrong with mine.

Ok, so after shuffling the tasks a little bit, a got to a configuration whose final result is the correct one. Let’s see if we can extract some interesting pieces of information out of it.

This is the first task disposition giving me the correct result that I found.

Of note that I said “the first task disposition”.
The reason why I said that, is because I figured out that there was not only one task disposition leading to the correct result.
Try to swap the first two tasks, [1,3] and [2,4]. That won’t change the final result.
The only difference would be that instead of having +3 and +2 in the beginning, we would have +4 and +1, but still, the third task, [10,11] (red bar) would start from 3.

Ok, noted, there might be more than one correct task disposition! Let’s compare now a correct one with a wrong one because we need to understand how to get to a correct solution, dodging the incorrect ones.

While I was shuffling and swapping the tasks to find an incorrect solution, I came across a particular task order that turned out to be instrumental to understand how to solve this Leetcode challenge:

On the left, we have the previously seen solution, on the right a second correct solution.
Don’t you see something of interest here? The fact that both the dispositions of the tasks have led to an optimal result might be misleading, but let’s analyze how they differ from each other. What if I removed the last task, [8,90]?

Can you see that now? The difference between the two dispositions is crucial now!
Looking at these images it might not be still crystal clear what is the main point to figure out the correct solution to this problem. So let’s move forward with our investigation.

Something really interesting is the behavior of the two cases when we extend the tasks. What do I mean by that?
Check out what would happen if we extended the first task from [1,3] to [1, 24]:

Fundamentally nothing has really changed.
The way we allocate energy is different, but the result is the same (unless the minimum covered all the other tasks, in that case, we would have a banal situation)

Let’s do the same with the second task, the green one.

Also in this case nothing chan… hey, wait a minute.

Here there is something deeply different from the previous case when we had a smaller minimum of the second task.

We previously stated that swapping the first and the second tasks didn’t have any impact on the final solution. If we swapped the two, actually the final solution wouldn’t change. But look at what you obtained. Does it ring a bell? If not, please, remove the yellow and the red tasks (the last two) and look at it again:

It should be clear now!
We extended the second task, and at some point, it because crucial to execute the green one before the first one!

As widely discussed it’s not only about the “minimum” value only, we tried to go down that path in the first approach, and we miserably failed.

So what seems to be of main importance to sort these tasks?

Maybe the “actual” value? It wouldn’t make sense, because the actual value is the part of the task that can’t overlap with anything. In other words, if you increase the “actual” value of a task, you simply move everything up, no question about it! It’s like a concrete block in our diagram (that’s why I represented the “actual” values with fully colored squares).

Not clear yet? Let’s try this last step then. When did executing the green task before the blue one become crucial?

You can deduce from this image that the first task (the blue one) has to be executed before the green one for the first two images when the second task (the green one) is [2,2] and [2,3].

When the green task becomes [2,4] it doesn’t matter which task gets executed first, the final result will be the same.

Starting from the last section of the image, when the green task becomes [2,5], it’s evident that it becomes crucial to execute it before the blue task.

I think we have a solution. We need to sort the tasks by the difference between the “minimum” and the “actual” values in descending order. That's it! The “minimum” and the “actual” value by themselves don’t give enough information, what we need to know is the difference between them.

The intuition
As mentioned at the beginning of this article, someone might have figured out the solution right after reading the test. The thing is that this problem has many practical applications. You can give the tasks different real-life meanings. Reading through the LeetCode discussion section, you will find several examples.
I’ll be trying to give you mine, hopefully so clear that you won’t have any doubts after it.

Imagine you’ve been given two tasks:
1. Replace the librarian. The librarian of the city needs to go to the dentist, so he asks you to replace him for 6 hours. It doesn’t matter when, if morning or evening, he just needs you to replace him for 6 hours during the day. You know that the library in your city is not busy at all, it will most probably take just 3 hours of your time, and the other 3 you’ll be free to do something else.
2. You have to conclude your article on Medium. You are almost done, you just need 4 hours to finish it off.

So, what would you do in this case? Would you rather complete your Medium article first, and then go to replace the librarian for the next 6 hours, or you would prefer to go to the library, spend 3 hours putting the books on the shelves (or doing whatever a librarian does), and once you are done, work on your Medium article for the next 3 hours (while you are getting paid by the library) and conclude it one hour later? I guess we would do the same.

This is not different from:
Input: [[3, 6],[4,4]]
Output: 7

The Code

Conclusions
I hope you enjoyed this article and hopefully learned something new. Let me know if you liked it by leaving a comment or clapping it. Have a great day!

“Any fool can know. The point is to understand.” — Albert Einstein