Minimum Time to Complete All Tasks solution in Python

Minimum Time to Complete All Tasks – Python Solution

Minimum Time to Complete All Tasks

Quick Links


class Solution:
    def findMinimumTime(self, tasks: list[list[int]]) -> int:
        kMax = 2000
        running = [False] * (kMax + 1)

        # Sort tasks by end.
        for start, end, duration in sorted(tasks, key=lambda x: x[1]):
            neededDuration = (duration -
                              sum(running[i] for i in range(start, end + 1)))
            # Greedily run the task as late as possible so that later tasks can run
            # simultaneously.
            i = end
            while neededDuration > 0:
                if not running[i]:
                    running[i] = True
                    neededDuration -= 1
                i -= 1

        return sum(running)

Problem Description

The “Minimum Time to Complete All Tasks” problem is akin to juggling multiple tasks without dropping any. You have a list of tasks, each defined by a start time, end time, and duration. Your goal is to determine the minimum time required to complete all tasks without any overlaps.

Think of it like planning a party where you need to fit all your friends into a limited time frame without losing your sanity!

Approach Explanation

The provided code sorts the tasks by their end times and calculates the time needed to complete each task. It allocates time as late as possible to maximize efficiency, allowing tasks to run simultaneously.

Time and Space Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of tasks.
Space Complexity: O(kMax) for the `running` list, which tracks time slots.

Real-World Example

Imagine you’re a chef preparing a multi-course meal for a dinner party. Each dish has a specific cooking time and must be ready by a certain time. You need to figure out how to cook everything without burning anything or letting the guests starve. This problem mirrors that scenario—finding the optimal way to complete all tasks within their time constraints!