Minimum Initial Energy to Finish Tasks - Practice Coding Problems

Minimum Initial Energy to Finish Tasks - Problem

You are given an array tasks where tasks[i] = [actual_i, minimum_i]:

actual_i is the actual amount of energy you spend to finish the i-th task.
minimum_i is the minimum amount of energy you require to begin the i-th 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.

Input & Output

Example 1 — Basic Case

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

› Output: 8

💡 Note: Starting with 8 energy: complete [4,8] (8≥8, energy=4), then [2,4] (4≥4, energy=2), then [1,2] (2≥2, energy=1)

Example 2 — Equal Requirements

$ Input: tasks = [[1,3],[2,4],[10,11]]

› Output: 32

💡 Note: Optimal order after sorting by overhead: [1,3], [2,4], [10,11]. Working backwards: need 11, then max(4,11+2)=13, then max(3,13+1)=14. But we need to check the reverse calculation properly.

Example 3 — Minimum Case

$ Input: tasks = [[1,1]]

› Output: 1

💡 Note: Only one task with minimum energy 1, so initial energy needed is 1

Constraints

1 ≤ tasks.length ≤ 10⁵
1 ≤ actual_i ≤ minimum_i ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tasks

Each task has [actual_energy, minimum_energy] requirements

Optimal Ordering

Sort by energy overhead (minimum - actual) descending

Calculate Energy

Work backwards to find minimum initial energy

Key Takeaway

🎯 Key Insight: Tasks with higher energy overhead must be done first to minimize initial energy

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that tasks with higher energy overhead (minimum - actual) should be completed first. The optimal approach uses greedy sorting by energy difference, then works backwards to calculate the minimum initial energy. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Orders	O(n! × n)	O(n)	Generate all possible task orders and find minimum initial energy
Greedy Sorting	O(n log n)	O(1)	Sort tasks by energy difference (minimum - actual) in descending order

Try All Orders — Algorithm Steps

Generate all permutations of tasks
For each order, simulate energy consumption
Track minimum initial energy across all orders

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Orders

Create all possible task arrangements

Simulate Each

Work backwards to find energy needed

Find Minimum

Return the smallest initial energy

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minInitial = INT_MAX;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int tasks[][2], int* indices, int start, int n) {
    if (start == n) {
        int energyNeeded = 0;
        for (int i = n - 1; i >= 0; i--) {
            int actual = tasks[indices[i]][0];
            int minimum = tasks[indices[i]][1];
            energyNeeded = (minimum > energyNeeded + actual) ? minimum : energyNeeded + actual;
        }
        if (energyNeeded < minInitial) {
            minInitial = energyNeeded;
        }
        return;
    }
    
    for (int i = start; i < n; i++) {
        swap(&indices[start], &indices[i]);
        permute(tasks, indices, start + 1, n);
        swap(&indices[start], &indices[i]);
    }
}

int solution(int tasks[][2], int n) {
    minInitial = INT_MAX;
    int* indices = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) indices[i] = i;
    
    permute(tasks, indices, 0, n);
    free(indices);
    return minInitial;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int tasks[100][2];
    int n = 0;
    char* ptr = line + 1; // skip '['
    
    while (*ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            tasks[n][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            tasks[n][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
            n++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(tasks, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! permutations, each taking O(n) time to simulate

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for current permutation and recursion stack

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Orders — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler