LogoKode$word
LeetCode 1665: Minimum Initial Energy to Finish Tasks – Java Greedy Solution Explained
LeetCode 1665: Minimum Initial Energy to Finish Tasks – Java Greedy Solution Explained

LeetCode 1665: Minimum Initial Energy to Finish Tasks – Java Greedy Solution Explained

Learn how to solve LeetCode 1665 Minimum Initial Energy to Finish Tasks using Greedy and Sorting in Java. Includes brute force intuition, optimal approach, dry run, time complexity, interview explanation, and common mistakes.

9 views
0
0
LeetCodeGreedy AlgorithmJavaSortingHardArray
Github icon
Github icon
Listen to articleAudio version
brillicode ad banner

Introduction

LeetCode 1665 – Minimum Initial Energy to Finish Tasks is an important greedy algorithm problem frequently asked in coding interviews.

The problem looks difficult initially because tasks can be completed in any order. The real challenge is finding the best order that minimizes the starting energy required.

This problem teaches:

  1. Greedy strategy
  2. Custom sorting
  3. Optimization thinking
  4. Simulation techniques
  5. Interview-level problem solving

Problem Link

🔗 https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks/

Problem Statement

You are given an array:

tasks[i] = [actuali, minimumi]

Where:

  1. actuali = energy spent after completing the task
  2. minimumi = minimum energy required to start the task

You can complete tasks in any order.

Return the minimum initial energy required to finish all tasks.

Example

Input

[[1,2],[2,4],[4,8]]

Output

8

Understanding the Problem

Suppose a task is:

[4,8]

This means:

  1. You need at least 8 energy to begin.
  2. After completing it, your energy decreases by 4.

If your current energy is:

10

After finishing:

10 - 4 = 6

Brute Force Approach

Intuition

Try every possible order of tasks and calculate the minimum starting energy needed.

Then return the smallest answer.

Why Brute Force Fails

If there are N tasks:

Total permutations = N!

For large constraints up to 10^5, brute force becomes impossible.

Brute Force Complexity

Time Complexity

O(N!)

Space Complexity

O(N)

Greedy Intuition

For every task:

[actual, minimum]

The value:

minimum - actual

represents how restrictive the task is.

Tasks with larger differences require high starting energy and should be completed earlier.

Key Greedy Observation

We should sort tasks in descending order of:

minimum - actual

This minimizes the extra starting energy required later.

Why This Greedy Works

Suppose we have:

A = [1,10]
B = [5,6]

Differences:

A -> 9
B -> 1

Task A is more restrictive.

If we delay task A, we may lose too much energy before attempting it.

So we perform tasks with larger (minimum - actual) first.

Optimal Greedy Approach

Steps

1. Sort Tasks

Sort tasks by:

(minimum - actual) in descending order

2. Maintain Current Energy

  1. curr = current available energy
  2. total = minimum initial energy required

3. Add Energy When Needed

If:

minimum > curr

Add extra energy.

4. Complete the Task

Reduce current energy by actual energy spent.

Java Greedy Solution

class Solution {

public int minimumEffort(int[][] tasks) {

Arrays.sort(tasks,
(a, b) -> (b[1] - b[0]) - (a[1] - a[0])
);

int total = 0;
int curr = 0;

for (int i = 0; i < tasks.length; i++) {

if (tasks[i][1] > curr) {

int diff = tasks[i][1] - curr;

curr += diff;
total += diff;
}

curr -= tasks[i][0];
}

return total;
}
}

Dry Run

Input

[[1,2],[2,4],[4,8]]

Step 1: Sort Tasks

Differences:

TaskDifference
[1,2]1
[2,4]2
[4,8]4

Sorted Order:

[[4,8],[2,4],[1,2]]

Step 2: Process Tasks

Task [4,8]

Need energy:

8

Current energy:

0

Add:

8

After completion:

8 - 4 = 4

Task [2,4]

Already have enough energy.

After completion:

4 - 2 = 2

Task [1,2]

After completion:

2 - 1 = 1

Final Answer

8

Time Complexity Analysis

Time Complexity

O(N log N)

Sorting dominates the complexity.

Space Complexity

O(1)

Ignoring sorting space.

Interview Explanation

In interviews, explain:

Tasks with larger (minimum - actual) are more restrictive because they require high starting energy. Performing them earlier prevents us from needing larger initial energy later.

This demonstrates strong greedy reasoning.

Common Mistakes

1. Sorting by Minimum Only

Incorrect because actual energy consumption also matters.

2. Sorting by Actual Only

Also incorrect.

The important factor is:

minimum - actual

3. Forgetting to Increase Current Energy

Always check:

if(tasks[i][1] > curr)

before performing the task.

FAQs

Q1. Why sort by (minimum - actual)?

Because it measures how restrictive a task is.

Q2. Is this Dynamic Programming?

No.

This is a Greedy + Sorting problem.

Q3. Why is this problem considered hard?

The greedy observation is difficult to identify.

The implementation itself is straightforward.

Conclusion

LeetCode 1665 is an excellent greedy problem for mastering:

  1. Custom sorting
  2. Greedy intuition
  3. Task scheduling
  4. Optimization techniques

The key idea is sorting tasks by:

minimum - actual

in descending order.

Once this intuition clicks, many advanced greedy interview problems become easier to solve.

Related Articles

LeetCode 2078: Two Furthest Houses With Different Colors | Java Solution Explained (Step-by-Step Guide)

LeetCode 2078: Two Furthest Houses With Different Colors | Java Solution Explained (Step-by-Step Guide)

Understand the problem deeply with examples, then master an optimal O(n) solution using a simple observation.

Read Article
Stack Problems Explained: NGR, NGL, NSR, NSL — The Four-Problem Family You Must Master

Stack Problems Explained: NGR, NGL, NSR, NSL — The Four-Problem Family You Must Master

Learn how to solve Next Greater Element (NGE), Previous Greater Element (NGL), Next Smaller Element (NSE), and Previous Smaller Element (NSL) in Java using a monotonic stack. Full GFG solutions explained with dry runs, edge cases, and real-world examples.

Read Article
Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions

Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions

Learn how to solve the Climbing Stairs problem using recursion, dynamic programming, and space optimization. Includes Java code, examples, and interview tips.

Read Article
Maximum Product Subarray

Maximum Product Subarray

LeetCode Question 152 Medium

Read Article
Ai Assistant Kas