We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Complete All Tasks

Number: 2657

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of tasks where each task is represented by [start, end, duration], determine the minimum total number of seconds during which a computer must be turned on to complete all tasks. Each task must be executed for a total of “duration” seconds (not necessarily continuous) within its inclusive time window [start, end]. The computer can run any number of tasks concurrently when it is on.

Key Insights

  • Sort tasks by their end times so that tasks with earlier deadlines are handled first.
  • For each task, count how many seconds have already been scheduled (turned-on) within its time window.
  • If additional seconds are needed, schedule them as late as possible (starting from the task's end) to maximize the chance of overlapping with future tasks.
  • Use a boolean or integer array (or similar structure) indexed by time to track which seconds have been scheduled.

Space and Time Complexity

Time Complexity: O(n * L) where n is the number of tasks and L is the length of the time range (up to 2000), which is feasible given the constraints. Space Complexity: O(L) for the scheduled time tracker.

Solution

The solution uses a greedy strategy:

  1. Sort the tasks by their ending time.
  2. For each task, scan its time interval [start, end] to count the seconds that are already scheduled.
  3. If the count is less than the required duration, add the missing seconds by scheduling them from the end of the interval backwards. This “late scheduling” ensures that these extra seconds might also serve upcoming tasks.
  4. Continue until all tasks meet their required durations.

This approach guarantees that the computer is turned on for the minimum necessary time, by efficiently overlapping the running intervals for different tasks.

Code Solutions

# Python solution for Minimum Time to Complete All Tasks

def min_time(tasks):
    # Sort tasks by their ending time
    tasks.sort(key=lambda x: x[1])
    # Array to mark if a second has been scheduled (0-indexed; we use 1-index based on constraints)
    scheduled = [False] * 2001
    total_on_time = 0

    # Process each task in order of increasing end time
    for start, end, duration in tasks:
        # Count how many seconds are already scheduled in the task's interval
        count = 0
        for t in range(start, end + 1):
            if scheduled[t]:
                count += 1

        # Calculate the additional seconds needed for this task
        needed = duration - count
        t = end
        # Schedule additional seconds as late as possible
        while needed > 0:
            if not scheduled[t]:
                scheduled[t] = True  # Schedule this second
                total_on_time += 1
                needed -= 1
            t -= 1  # Move to an earlier second
    return total_on_time

# Example usage:
tasks = [[2,3,1],[4,5,1],[1,5,2]]
print(min_time(tasks))  # Expected output: 2
← Back to All Questions