How do you solve Minimum Processing Time on LeetCode?

Minimum Processing Time (LeetCode #2895) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Assigning longer tasks to processors that become available earlier minimizes overall completion time.

What is the time complexity of Minimum Processing Time?

The optimal solution for Minimum Processing Time runs in O(n log n) time and uses O(n) space. The time complexity is dominated by the sorting steps, which take O(n log n). The space complexity is O(n) for storing finish times.

What is the brute force solution for Minimum Processing Time?

The brute force approach for Minimum Processing Time is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves trying every possible assignment of tasks to processors and calculating the time taken for each assignment. This is simple but inefficient, as it explores all combinations. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Minimum Processing Time?

Minimum Processing Time uses the following concepts: Array, Greedy, Sorting. The recommended patterns to study are: Greedy, Sorting.

What are the interview tips for Minimum Processing Time?

Always start with a brute-force solution to understand the problem deeply. Look for patterns in the problem, such as sorting, greedy approaches, or dynamic programming. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Minimum Processing Time?

Not considering the order of task assignment can lead to suboptimal solutions. Failing to account for the maximum finish time across all processors.

#2895

Minimum Processing Time

Medium

ArrayGreedySortingGreedySorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal solution leverages sorting and greedy assignment. By sorting both the processor times and task durations, we can efficiently assign tasks to minimize the overall completion time.

⚙️

Algorithm

4 steps

1Step 1: Sort the processorTime array in ascending order.
2Step 2: Sort the tasks array in descending order.
3Step 3: Assign the longest tasks to the processors with the earliest available times, ensuring each processor gets 4 tasks.
4Step 4: Calculate the finish time for each processor and return the maximum finish time.

solution.py9 lines

1def minProcessingTime(processorTime, tasks):
2    processorTime.sort()
3    tasks.sort(reverse=True)
4    n = len(processorTime)
5    finish_times = [0] * n
6    for i in range(len(tasks)):
7        processor_index = i // 4
8        finish_times[processor_index] = max(finish_times[processor_index], processorTime[processor_index] + tasks[i])
9    return max(finish_times)

ℹ

Complexity note: The time complexity is dominated by the sorting steps, which take O(n log n). The space complexity is O(n) for storing finish times.

1Assigning longer tasks to processors that become available earlier minimizes overall completion time.
2Sorting both the processors and tasks helps in efficiently pairing them.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.