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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Complete All Tasks

Difficulty: Hard

Problem Description

You are given a 2D integer array tasks where tasks[i] = [start_i, end_i, duration_i] indicates that the i-th task should run for a total of duration_i seconds within the inclusive time range [start_i, end_i]. Return the minimum time during which the computer should be turned on to complete all tasks.

Key Insights

  • The computer can run tasks simultaneously.
  • Tasks can be split within their allowed time ranges.
  • The goal is to minimize the total time the computer is turned on while ensuring all task durations are met.

Space and Time Complexity

Time Complexity: O(N log N) - where N is the number of tasks, due to sorting. Space Complexity: O(N) - for maintaining the active tasks in a data structure.

Solution

To solve the problem, we can use a greedy approach combined with a priority queue (or min-heap) to manage the tasks effectively. The steps are as follows:

  1. Sort the tasks based on their ending time. This allows us to focus on the earliest finishing tasks first, minimizing idle time.
  2. Use a min-heap to keep track of the ongoing tasks and their durations. As we iterate through time, we can add tasks to the heap when their start time is reached.
  3. Calculate the total active time by processing tasks from the heap and fulfilling their required durations within their allowed time frames.

This approach ensures we utilize the available time slots efficiently, minimizing the total time the computer is turned on.

Code Solutions

import heapq

def minTimeToComplete(tasks):
    # Sort tasks based on their end time
    tasks.sort(key=lambda x: x[1])
    min_time = 0
    active_tasks = []
    current_time = 0
    
    for start, end, duration in tasks:
        # Process tasks that can no longer run
        while active_tasks and current_time < start:
            end_time, remaining_duration = heapq.heappop(active_tasks)
            time_to_run = min(remaining_duration, start - current_time)
            min_time += time_to_run
            remaining_duration -= time_to_run
            current_time += time_to_run
            if remaining_duration > 0:
                heapq.heappush(active_tasks, (end_time, remaining_duration))
        
        # Add the current task to the active tasks
        heapq.heappush(active_tasks, (end, duration))
        current_time = max(current_time, start)
        
    # Final processing of remaining tasks
    while active_tasks:
        end_time, remaining_duration = heapq.heappop(active_tasks)
        time_to_run = min(remaining_duration, end_time - current_time + 1)
        min_time += time_to_run
        current_time += time_to_run

    return min_time
← Back to All Questions