Minimum Time to Complete All Tasks — LeetCode 2589 Python Solution

The problem

There is a computer that can run an unlimited number of tasks at the same time. You are given a 2D integer array tasks where tasks[i] = [starti, endi, durationi] indicates that the ith task should run for a total of durationi seconds (not necessarily continuous) within the inclusive time range [starti, endi].

Example

Input

tasks = [[2,3,1],[4,5,1],[1,5,2]]

Output

2

Explanation

- The first task can be run in the inclusive time range [2, 2].

Python solution

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1])
        vis = [0] * 2010
        ans = 0
        for start, end, duration in tasks:
            duration -= sum(vis[start : end + 1])
            i = end
            while i >= start and duration > 0:
                if not vis[i]:
                    duration -= 1
                    vis[i] = 1
                    ans += 1
                i -= 1
        return ans

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2589. Minimum Time to Complete All Tasks is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems