We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Initial Energy to Finish Tasks

Number: 1784

Difficulty: Hard

Paid? No

Companies: Akuna Capital

Problem Description

You are given an array of tasks, where each task is represented as [actual, minimum]. For each task, you need at least “minimum” energy to start it, and after completing the task, you lose “actual” energy (i.e. your energy decreases by actual). You can complete the tasks in any order. Return the minimum initial energy required so that you can finish all tasks.

Key Insights

  • The order of tasks is flexible – choose an order that minimizes extra energy boosts.
  • Tasks that demand a high minimum energy relative to energy spent (i.e. with a large difference (minimum - actual)) are “harder” because they force your energy to be high at the moment you start them.
  • Sorting the tasks in descending order of (minimum - actual) ensures that the tasks with the highest “buffer” requirement are handled first.
  • While simulating the process, if your current energy is less than the minimum required for a task, you must “inject” the difference into your energy. This cumulative extra energy gives the answer.

Space and Time Complexity

Time Complexity: O(n log n) because we sort the tasks. Space Complexity: O(1) extra space (ignoring the input array space).

Solution

The solution uses a greedy strategy. First, sort the tasks in descending order of (minimum - actual) – this prioritizes tasks that require a larger energy buffer. Initialize two variables: one for the additional energy needed (ans) and another for the current energy. Then, iterate over the sorted tasks. For each task, if the current energy is less than the task’s minimum requirement, “inject” the needed extra energy and update both the result and current energy. Finally, subtract the actual energy cost of the task. This simulation guarantees that you meet every task’s requirement using the minimum initial energy.

Code Solutions

def minimumInitialEnergy(tasks):
    # Sort tasks by (minimum - actual) in descending order.
    tasks.sort(key=lambda task: (task[1] - task[0]), reverse=True)
    # Initialize the additional energy needed and the current energy.
    additional_energy_needed = 0
    current_energy = 0
    # Process each task in sorted order.
    for actual, minimum in tasks:
        # If current energy is less than the minimum required, add the difference.
        if current_energy < minimum:
            diff = minimum - current_energy
            additional_energy_needed += diff
            current_energy += diff
        # Spend the energy required to complete the task.
        current_energy -= actual
    return additional_energy_needed

# Example usage:
tasks = [[1,2],[2,4],[4,8]]
print(minimumInitialEnergy(tasks))  # Output: 8
← Back to All Questions