Minimum Time to Complete All Tasks

Hard
868.

Minimum Time to Complete All Tasks

Minimum Time to Complete All Tasks is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Rubrik interviews.

tasks[i] = [start_i, end_i, duration_i] means task i must run for duration_i whole seconds, each of them inside the inclusive range [start_i, end_i] (not necessarily consecutive).

The computer may run any number of tasks at the same time. Return the minimum number of seconds the computer has to be switched on.

Example 1

Input
tasks = [[2,3,1],[4,5,1],[1,5,2]]
Output
2
Explanation
Running at seconds 2 and 5 covers everything.

Example 2

Input
tasks = [[1,3,2],[2,5,3],[5,6,2]]
Output
4

Example 3

Input
tasks = [[1,1,1]]
Output
1

Constraints

  • 1 <= tasks.length <= 2000
  • 1 <= start_i <= end_i <= 2000
  • 1 <= duration_i <= end_i - start_i + 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} tasks
 * @return {number}
 */
var findMinimumTime = function(tasks) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Time to Complete All Tasks — Problem & Solution

Minimum Time to Complete All Tasks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Time to Complete All Tasks is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Rubrik interviews.

  • Difficulty: Hard
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Google, Rubrik
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

tasks[i] = [start_i, end_i, duration_i] means task i must run for duration_i whole seconds, each of them inside the inclusive range [start_i, end_i] (not necessarily consecutive).

The computer may run any number of tasks at the same time. Return the minimum number of seconds the computer has to be switched on.

Example 1

Input: tasks = [[2,3,1],[4,5,1],[1,5,2]]
Output: 2
Explanation: Running at seconds 2 and 5 covers everything.

Example 2

Input: tasks = [[1,3,2],[2,5,3],[5,6,2]]
Output: 4

Example 3

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

Constraints

  • 1 <= tasks.length <= 2000
  • 1 <= start_i <= end_i <= 2000
  • 1 <= duration_i <= end_i - start_i + 1

Hints for Minimum Time to Complete All Tasks

  1. Hint 1

    Sort the tasks by their deadline, then satisfy each one using seconds as late as possible.

  2. Hint 2

    Seconds already switched on for earlier tasks count towards the current one for free.

  3. Hint 3

    Turning on the latest available seconds maximises the chance that later tasks can reuse them.

How to solve Minimum Time to Complete All Tasks

Process tasks in order of deadline, and pay for each one as late as possible. Late seconds are the most likely to fall inside the windows of the tasks still to come, so they get reused most often.

Approach

  1. Sort the tasks by end.
  2. For each task, count how many seconds in [start, end] are already on and subtract them from its duration.
  3. For whatever is still needed, switch on the latest free seconds in the window, walking backwards from end.

Why it works

Exchange argument: take an optimal schedule and the earliest task by deadline. Any second it uses can be swapped for a later free second inside its window without breaking it, and a later second is contained in at least as many future windows — because the tasks are processed in deadline order, every later task's window extends at least as far right. Repeating the swap turns the optimal schedule into the greedy one.

Complexity

  • Time — O(n · T) where T is the time range
  • Space — O(T)

Pitfalls

  • Sorting by start time instead of by deadline breaks the exchange argument.
  • Seconds already on must be counted, not re-paid.
  • Filling from the start of the window instead of the end wastes reuse and over-counts.

Reference solution

Python

from typing import List

def findMinimumTime(tasks: List[List[int]]) -> int:
    t = sorted(tasks, key=lambda x: x[1])
    on = [False] * 2002
    total = 0
    for s, e, d in t:
        for x in range(s, e + 1):
            if on[x]:
                d -= 1
        x = e
        while d > 0:
            if not on[x]:
                on[x] = True
                total += 1
                d -= 1
            x -= 1
    return total

Java

public static int findMinimumTime(int[][] tasks) {
    int[][] t = tasks.clone();
    Arrays.sort(t, (a, b) -> Integer.compare(a[1], b[1]));
    boolean[] on = new boolean[2002];
    int total = 0;
    for (int[] task : t) {
        int s = task[0], e = task[1], d = task[2];
        for (int x = s; x <= e; x++) if (on[x]) d--;
        for (int x = e; d > 0; x--) {
            if (!on[x]) {
                on[x] = true;
                total++;
                d--;
            }
        }
    }
    return total;
}

C++

int findMinimumTime(vector<vector<int>>& tasks) {
    vector<vector<int>> t = tasks;
    sort(t.begin(), t.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    vector<bool> on(2002, false);
    int total = 0;
    for (auto& task : t) {
        int s = task[0], e = task[1], d = task[2];
        for (int x = s; x <= e; x++) if (on[x]) d--;
        for (int x = e; d > 0; x--) {
            if (!on[x]) {
                on[x] = true;
                total++;
                d--;
            }
        }
    }
    return total;
}

JavaScript

var findMinimumTime = function(tasks) {
    var t = tasks.slice().sort(function(a, b) { return a[1] - b[1]; });
    var on = [];
    for (var i = 0; i < 2002; i++) on.push(false);
    var total = 0;
    for (var k = 0; k < t.length; k++) {
        var s = t[k][0], e = t[k][1], d = t[k][2], x;
        for (x = s; x <= e; x++) if (on[x]) d--;
        for (x = e; d > 0; x--) {
            if (!on[x]) { on[x] = true; total++; d--; }
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms