leetcode 1665 |Minimum Initial Energy to Finish Tasks | Greedy | Binary Search | Leetcode POTD| DSA

Hinzugefügt: 2026-05-12

[00:00:00]And good morning to everyone. So, today lead code question is 1665, which is minimum initial energy to finish task.

[00:00:07]So, basically in this question we are given an array task where task of I has two things actual I and minimum I. So, actual of I is basically the actual amount of energy that we have to spend on the I'th task to finish it. And minimum of I is basically the minimum amount of energy which we require to begin the I'th task. So, here it is given an example that 10 and 12.

[00:00:34]So, 12 is the minimum energy. 12 is the minimum energy that we require to start this task. And suppose our current energy is 11, then we cannot then we cannot start this task. But, if our current energy is 13, that means 13 is greater than 12, that is the minimum energy. So, we can start the this task.

[00:00:54]And when we complete this task, so our energy is 13 and how much we require? 10 we require. So, 13 minus 10 So, three is left with us, right? So, this way we are given an array of task. And what we have to do is it is given that we can finish the task in any order, right? And at the end what we need is we need to the tell them the minimum initial energy.

[00:01:18]Minimum initial amount of energy that we need to finish all the task, right?

[00:01:25]So, let's start. So, let's see some examples to get the question more clearly. So, here we are given task 1 2 2 4 4 8, right? So, we are starting with eight. We have to take energy is equal to eight, right? So, first we execute this task, right? So, how much minimum energy it requires? Eight. So, we have taken So, we have sufficient energy to start this task. So, when we complete this task, how many energy we are left? We are left with eight minus how much it requires?

[00:01:57]four. So, we are left with four.

[00:02:00]Now, let's start with let's execute this task. So, how much energy it requires four and how much we have we have four.

[00:02:08]So, when we complete this task, how much it requires? It requires two. So, four minus two is two. So, we are left with energy two. How much this task require?

[00:02:18]It requires two.

[00:02:20]So, uh how much we have? We have also two.

[00:02:25]So, how much it requires? It requires one. So, we are left with one. So, with energy is equal to eight with energy is equal to eight, we have we have executed all the three task. Now, let's say suppose we have energy is equal to seven. We if we have taken energy is equal to seven, then if you execute this task, this task require minimum energy as eight and our energy is seven, which is lesser than lesser than minimum. So, we can't execute this task. So, our answer is eight, right?

[00:03:00]Now, let's see this example.

[00:03:03]So, we have again these all the task and now we have to execute all these task and find the minimum energy that we require.

[00:03:12]So, here the answer is 32. So, let's say we have taken this 32, right?

[00:03:19]And now, we have executed the first task. We have executed the first task.

[00:03:25]So, now after executing first task, our energy will be 32 minus one, which is 31.

[00:03:30]31, then we have executed second task.

[00:03:32]So, 31 minus two is 29.

[00:03:36]Then we executed third task.

[00:03:39]So, 29 minus 10 is 19.

[00:03:42]Then we have energy here we have energy 19, which is greater than 12. So, after executing, we are left with energy is equal to nine.

[00:03:51]Then we have executed this task. So, 32 is the minimum energy. 32 is the minimum energy that is required to satisfy both the conditions of minimum constraints and we have so that we left with some and we have sufficient actual energy.

[00:04:11]Let's see the constraints.

[00:04:13]So, the number of tasks that we have can be up to 10 ^ 5, right? So, we have to think of some solution of either big of n or big of n log n, right? n log n.

[00:04:28]Because our array length is up to 10 ^ 5 and also actual and minimum values can be up to 10 ^ 4, right? So, let's see the approach. So, basically each task has two things, actual and minimum, where minimum is the minimum energy that we require before starting a task and actual is the energy required to complete the task. Right? And our goal is to find the minimum initial energy that we require to complete all the task. So now, what we need? First, we need to find the order of the task in which we can execute that them such that such that we get the minimum energy E, right? So, now what is our goal? Goal is to first find the order of the task to execute them. So, let's suppose we have two tasks, A and B, right? Where A is the actual energy consumed M M M is the minimum energy required. Now, what we want to determine? We want to determine whether we execute A before B, we execute A before B or B before A, like in which order we execute them such that we require minimum energy. So, let's say we execute A before B.

[00:05:47]A before B, and suppose our initial energy is E.

[00:05:51]Our initial energy is E, right?

[00:05:54]So So, for A, we have A1, M1. M1. Then, to execute A, our energy should be greater than equal to M1, right?

[00:06:05]That is the minimum condition should be satisfied, right? So after completing A, how much energy we are left we are left with energy E minus A1 because it will consume A1 energy.

[00:06:20]Then, we have B. So, for B we are given A2, M2. Now, to execute Now, to execute B the energy that we have, that is E minus A1, should be greater than the minimum greater than or equal to the minimum, that is M2. So, here if we shift this A1 this side, then E should be greater than or equal to A1 plus M2.

[00:06:46]Right?

[00:06:47]So, this is the condition. So, if you see the total minimum energy that we need is I is maximum of maximum of M1, A1 plus M2. Like maximum of these two, right? So, if you execute A before B, if you execute A before B, then the minimum energy sh is equal to maximum of maximum of M1, A1 plus M2.

[00:07:18]A1 plus M2.

[00:07:20]Right?

[00:07:24]Similarly, if you have to execute B before A.

[00:07:27]If we have to execute B before A then the minimum energy needed is maximum of M2, A2 plus M1.

[00:07:38]Right? M2, A2 plus M1. Right?

[00:07:42]Now, we have this is case two and the above one is a case one.

[00:07:48]So, which case we will taking? We will take that case which will give us less energy. Which will give us less energy.

[00:07:56]And we are assuming that we execute A before B. We are We want to execute A before B. That means That means the minimum energy of case A, which is maximum of M1 {comma} A1 + M2 should be less than uh minimum energy of the second case, that is B before A, right? So, this is a This is the expression that we have got.

[00:08:22]Right? So, if you have to execute A before B, A before B, then energy that we get in case one should be lesser than energy in case B because our overall goal is to minimize the energy.

[00:08:37]So, the expression that we get from this thing is that maximum of M1 {comma} A1 + M2 should be less than maximum of M2 {comma} A2 + M1, right?

[00:08:52]So, the important observation from here is since M1 is always be greater than A1 and M2 will always be greater than or A2, right? And we also know that A1 + M2 will always be greater than equal to M2 and A2 + M1 A2 + M1 will always be greater than M1, right? So, these expressions will always be will always hold. So, if we see A1 + M2 A1 + M2 dominates the left max. Left max means this part.

[00:09:28]A1 + M2 will dominate this part.

[00:09:32]And A2 + M1 A2 + will A2 + M1 dominates the right part, this part, right?

[00:09:39]A2+M1 dominates this part. And A1+M2 dominates this part, right? See here, A2+M1 will always be greater than this M1, will always be greater than this M1.

[00:09:51]Similarly, A1+M2, A1+M2 is greater than M2, right?

[00:09:57]So, here A1+M2 dominates this part.

[00:10:01]And A2+M1 dominates this part. Right?

[00:10:05]So, we compare the So, instead of comparing this whole equation, what we'll do is we'll compare A1+M2 from the left part, A1+M2 from the left part, and A2+M1 from the right part, right? And then we If we rearrange So, M2-A2, M2-A2 should be less than M1-A1.

[00:10:31]Should be less than M1-A1.

[00:10:34]When If you have to execute A before B.

[00:10:38]If you have to execute A before B, then this condition, that is M2-A2 is lesser than M1-A1 should hold if you have to execute A before B. That means That means M1-A1, M1-A1 should be greater than M2-A2, right? If you have to execute A before B.

[00:10:58]So, So, what we get from here? We get that the task the task which has which has larger minimum minus actual difference, which has larger minimum minus actual difference, should execute first. Should execute execute first, right? This is what we get from this thing, right? Because we have assumed that we have to execute A before B, and we are getting the minimum minus actual difference of A should be greater than minimum minus actual difference of two if you have to execute A before B and where minimum minus actual represents the extra energy that we that is required by the task. So, basically if a require a task requires huge starting energy but consumes little energy, that means it is restrictive.

[00:11:49]That means we have to execute it first, right?

[00:11:52]So, we get that the task with minimum minus actual difference, the those tasks that has minimum minus actual difference larger should be should be executed first should be executed first. So, now what we'll do is we'll we will sort our array. We will sort our array based on the difference based on the difference that is minimum minus actual to find the order of our tasks, right? So, once we sort the array, that means then we get the order. Now, what we need to do is we need to find the minimum energy. We need to find the minimum energy required to execute all the task to required to execute all the task. So, now one way first way is we can use binary search over here. We can use binary search over here and then find then find the minimum energy. So, it will take n log n time n log n time, right?

[00:12:55]For binary search and for binary search our range will be from 1 to 10 ^ 14.

[00:13:01]Now, how 10 ^ 14? So, total elements that we have is 10 ^ 5 and and each element can be up to 10 ^ 4, right?

[00:13:13]So, 10 ^ 4 + 10 ^ 4 which is 10 ^ 5 into 10 ^ 4, which is 10 ^ 9. So, maximum range will be 10 ^ 9. So, this is a range for binary search. Then we find for Then we find the mid and we check whether it is feasible whether it is feasible to complete all the task with the this energy. So, if we if we complete the task with the mid energy, then we then we search in the left half. Left half.

[00:13:47]Right? Else we Else we shift in the right half. Right?

[00:13:52]So, this way we will find the minimum energy. So, this is method one which will take n log n time. The other method that we can opt is Basically, we have taken two variables, energy which will store the current available energy with us and the answer. Answer is stored minimum initial energy that we need. So, initially we have declared both as zero.

[00:14:15]And then what we'll do is we'll process each task one by one in the sorted order. Right?

[00:14:20]So, we have for actual For every task we have two things, actual and minimum.

[00:14:25]Now, if our current energy if our current energy is stored that is stored in variable energy is smaller than minimum energy required by the task is smaller than minimum energy required by the task, that means that means we cannot start the task.

[00:14:42]That means we cannot start our task and we have to increase our initial energy.

[00:14:48]We have to increase our initial energy and what we need We need minimum energy.

[00:14:54]Right? So, by how much we have to increase? So, we have to increase by minimum minus energy. Right? Minimum minus energy because we have we have energy and we need minimum. We need minimum. So, this difference This difference should be added to to energy to reach at minimum.

[00:15:13]Right? So, how much we have increased?

[00:15:15]We have increased by D. So, that we'll add That we will add to the answer. That we'll add to the answer. and now our energy will become equal to minimum.

[00:15:26]So, now we have enough energy to perform the current task, right? And after completing this task, our energy will be decreased by actual because actual is the amount of energy that the task will consume. So, we reduce energy is equal to energy minus actual. And this thing we keep repeating for all the task. So, once again, I'll tell you.

[00:15:48]If our energy is less If our energy is less than the minimum of the current task, then we increase our energy by minimum minus energy and add that particular energy to the answer. And once our energy become equals to the minimum energy that we require, then then we uh complete the task and our our energy will be decreased by actual, right?

[00:16:13]And once we process all the task, then answer will store the minimum initial energy that we require. So, we return our answer. So, let's try to uh see uh how it works. So, we have taken tasks 1 2 2 4 4 8. So, then first we sort by minimum minus actual difference in descending order, right? Because we have to process those tasks first that has minimum minus actual difference greater, right?

[00:16:44]So, after sorting, we get this as the array and then we have initialized energy is equal to 0 and answer is equal to 0. Now, our first task is first task is 4, 8. That means it requires a minimum eight energy to start the task.

[00:17:00]But how much energy how much energy we have? Zero. So, so we have to increase the energy by 8 minus 0 is 8. So, we have to increase the energy by 8. So, our answer will be now eight, that is 0 + 8. And now our energy has become eight, right? Now we have sufficient energy to start the task, so we perform the task. So our energy will become eight minus four, so four is the actual energy that we have reduced. So now how much energy we are left with? We are left with energy as four.

[00:17:32]So now next we move to the next task. So next task is two comma four, and it requires a minimum energy of four, and we already have that energy, so we directly perform this task. So when we perform this task, how much actual energy it will take? It will take two.

[00:17:47]So how much we are left with? We are left with We are left with Earlier we have four, this will require two, so we are left with two.

[00:17:55]So now again we move to the next task.

[00:17:57]Next task is one comma two, and the energy that we have is two, and it also requires a minimum energy of two.

[00:18:04]So we can directly perform because we have the sufficient energy with us.

[00:18:08]So the energy left after this task is two minus one, one. So we have performed We have performed all the task. So our final answer is eight, that is we require a minimum of minimum energy of eight to perform all the three task.

[00:18:25]So let's see the code part. So first of all we sort all the task all the task on the basis of the difference, minimum minus actual, minimum minus minimum minus actual and in descending order, in descending order, right? That's why we have d1 is greater than d2.

[00:18:46]Right?

[00:18:48]So once we get the sorted task, now our our our goal is to find the energy.

[00:18:53]So we have taken answer is equal to zero and energy is equal to zero, and then then we then we execute each task one by one. So we have taken the actual energy and minimum energy of the task. Now if our if our energy if our current energy is less than the minimum energy that we require, then we have to increase our initial energy.

[00:19:16]So, how much we have to increase? The difference of minimum minus energy by which we increase, right? So, now we have updated our answer that we have added the energy that we increase to the answer, and then now our energy is equal to minimum, right?

[00:19:32]And now we perform the task. So, while performing the task by we decrease the energy by actual energy that we require, right?

[00:19:43]So, after processing all the task, we return the answer. We return the answer.

[00:19:49]So, I hope I'm able to explain you the solution properly. So, if you like the video, please make sure to like, share, and subscribe the channel. Thank you.