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 Processing Time

Number: 3151

Difficulty: Medium

Paid? No

Companies: Adobe, Akuna Capital, Nutanix

Problem Description

You are given an array processorTime where each element is the time at which a processor becomes available. Each processor has 4 cores and there are exactly 4×n tasks given in the array tasks (each task taking some time to execute). Each task must be assigned to a unique core and a processor can only process 4 tasks (one per core). When a processor p starts executing a task with time t, the finish time is p + t. The goal is to distribute the tasks among the processors so that all tasks are completed and the overall finish time (i.e. the maximum finish time among all processors) is minimized.

Key Insights

  • There are exactly 4 tasks per processor and tasks can be arbitrarily assigned to cores.
  • The finish time for a processor is determined by its available time plus the maximum time among the 4 tasks it processes.
  • To minimize the overall maximum finish time, larger tasks should ideally be paired with processors that are available earlier.
  • A binary search on the candidate “maximum finish time” can be used to decide if all tasks can be assigned under that threshold.
  • A greedy check works by assigning tasks in descending order (largest first) to processors in ascending order (smallest available time first).

Space and Time Complexity

Time Complexity: O(totalTasks * log(max(processorTime)+max(tasks))). In worst-case, total tasks = 4*n and n ≤ 25,000 with log factor coming from binary search. Space Complexity: O(n + totalTasks) for sorting the processor and tasks arrays.

Solution

The idea is to use binary search to find the smallest maximum finish time M such that all tasks can be assigned properly. For a candidate M, we check each processor (sorted in increasing order of availability) and attempt to assign it 4 tasks from the list of all tasks (sorted in descending order so that the largest tasks get the “best” – smallest – processor). For each processor with available time p, it can only process a task t if p + t ≤ M, i.e. t ≤ M - p. If it is not possible to assign 4 tasks for each processor under M, then M is too small. This greedy assignment check is performed for every candidate M in the binary search. Finally, the binary search converges on the minimum M for which an assignment exists.

Code Solutions

def minProcessingTime(processorTime, tasks):
    # Sort processor available times in ascending order.
    processors = sorted(processorTime)
    # Sort tasks in descending order (largest tasks first).
    tasks_desc = sorted(tasks, reverse=True)
    
    n = len(processors)
    total_tasks = len(tasks)
    
    # Set lower bound (smallest finish time) and upper bound (largest possible finish time)
    lo = min(processors) + min(tasks)
    hi = max(processors) + max(tasks)
    
    def canFinish(M):
        # Greedily assign tasks to processors in order.
        task_index = 0
        for p in processors:
            bound = M - p  # This processor can only handle tasks of size <= bound.
            # Each processor must be assigned 4 tasks.
            for _ in range(4):
                if task_index >= total_tasks:
                    break
                # If the current largest remaining task fits within the bound, assign it.
                if tasks_desc[task_index] <= bound:
                    task_index += 1
                else:
                    # The current task is too heavy to be assigned to processor with start p.
                    return False
        # If all tasks have been assigned, the candidate M works.
        return task_index == total_tasks

    result = hi
    # Binary search for the smallest M that allows assignment of all tasks.
    while lo <= hi:
        mid = (lo + hi) // 2
        if canFinish(mid):
            result = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return result

# Example usage:
if __name__ == "__main__":
    print(minProcessingTime([8,10], [2,2,3,1,8,7,4,5]))  # Expected output: 16
    print(minProcessingTime([10,20], [2,3,1,2,5,8,4,3]))  # Expected output: 23
← Back to All Questions