Minimum Initial Energy to Finish Tasks - Video Solutions

Problem Overview: You are given tasks where each task has two values: the actual energy spent to complete it and the minimum energy required to start it. The goal is to determine the minimum initial energy needed so you can complete every task in some order without your energy dropping below the required threshold.

Approach 1: Binary Search for Minimum Energy (O(n log n) time, O(1) space)

This approach treats the answer as a search space. Assume a candidate starting energy and simulate whether all tasks can be completed. To maximize feasibility, sort tasks so those with the largest gap between minimumRequired and actualCost are handled first. For each candidate value, iterate through tasks, check if current energy satisfies the minimum requirement, and subtract the actual cost. Binary search narrows the smallest starting energy that passes the simulation. Sorting dominates the runtime, resulting in O(n log n) time with constant extra space.

Approach 2: Greedy Sorting by Energy Surplus (O(n log n) time, O(1) space)

The key insight: tasks with a larger difference between required energy and actual cost are more restrictive and should be executed earlier. Sort tasks by (minimumRequired - actualCost) in descending order. Then iterate through the sorted tasks while maintaining your current energy. If the current energy is less than the task's required minimum, increase the initial energy so the requirement is satisfied. After completing the task, subtract its actual cost. This greedy ordering ensures you never face a task later that requires more upfront energy than you can afford. The sort step takes O(n log n) time and the single pass simulation is O(n), with O(1) additional space.

Both strategies rely on ordering tasks by how restrictive they are. The greedy version computes the minimum energy directly and is simpler to implement than repeatedly validating candidates with binary search.

Recommended for interviews: The greedy sorting strategy is what most interviewers expect. Recognizing that tasks with the largest minimumRequired - actualCost gap must be handled first demonstrates strong intuition with greedy algorithms and sorting. The binary search method shows an alternative reasoning path but is usually considered less direct. Understanding both strengthens your problem-solving toolkit for array-based scheduling and ordering problems.