Minimum Initial Energy to Finish Tasks

This page explains Java solution to problem Minimum Initial Energy to Finish Tasks using Greedy algorithm.

Problem Statement

You are given an array tasks where tasks[i] = [actuali, minimumi]:

• actuali is the actual amount of energy you spend to finish the ith task.
• minimumi is the minimum amount of energy you require to begin the ith 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: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Explanation: Starting with 8 energy, we finish the tasks in the following order:
- 3rd task. Now energy = 8 - 4 = 4.
- 2nd task. Now energy = 4 - 2 = 2.
- 1st task. Now energy = 2 - 1 = 1.
Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.

Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32
Explanation: Starting with 32 energy, we finish the tasks in the following order:
- 1st task. Now energy = 32 - 1 = 31.
- 2nd task. Now energy = 31 - 2 = 29.
- 3rd task. Now energy = 29 - 10 = 19.
- 4th task. Now energy = 19 - 10 = 9.
- 5th task. Now energy = 9 - 8 = 1.

Solution

package com.vc.hard;

import java.util.Arrays;
import java.util.Comparator;

class MinimumInitialEnergyToFinishTasks {
    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, new Comparator<int[]>(){
            public int compare(int[] x, int[] y) {
                return Integer.compare(x[1] - x[0], y[1] - y[0]);
            }
        });

        int res = 0;
        for(int[] task: tasks) {
            res = Math.max(res + task[0], task[1]);
        }
        return res;
    }
}

Time Complexity

O(N log N) Where
N is total number of elements in an input array

Space Complexity

O(1)