Minimum Time to Complete All Tasks — Hard Problem & Solution

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard