# Minimum Processing Time
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-processing-time)
Canonical: https://scaleengineer.com/dsa/problems/minimum-processing-time
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
You have a certain number of processors, each having 4 cores. The number of tasks to be executed is four times the number of processors. Each task must be assigned to a unique core, and each core can only be used once.

You are given an array `processorTime` representing the time each processor becomes available and an array `tasks` representing how long each task takes to complete. Return the _minimum_ time needed to complete all tasks.

**Example 1:**

**Input:** processorTime = \[8,10\], tasks = \[2,2,3,1,8,7,4,5\]

**Output:** 16

**Explanation:**

Assign the tasks at indices 4, 5, 6, 7 to the first processor which becomes available at `time = 8`, and the tasks at indices 0, 1, 2, 3 to the second processor which becomes available at `time = 10`. 

The time taken by the first processor to finish the execution of all tasks is `max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16`.

The time taken by the second processor to finish the execution of all tasks is `max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13`.

**Example 2:**

**Input:** processorTime = \[10,20\], tasks = \[2,3,1,2,5,8,4,3\]

**Output:** 23

**Explanation:**

Assign the tasks at indices 1, 4, 5, 6 to the first processor and the others to the second processor.

The time taken by the first processor to finish the execution of all tasks is `max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18`.

The time taken by the second processor to finish the execution of all tasks is `max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23`.

**Constraints:**

* `1 <= n == processorTime.length <= 25000`
* `1 <= tasks.length <= 105`
* `0 <= processorTime[i] <= 109`
* `1 <= tasks[i] <= 109`
* `tasks.length == 4 * n`

# Approaches
## Sorting with Naive Pairing (Incorrect Greedy)
A straightforward but incorrect approach is to sort both the processor available times and the task durations and then pair them in the same order. This means the earliest available processor is assigned the four shortest tasks, the second earliest processor gets the next four shortest tasks, and so on.
**Time:** O(M log M + N log N), where N is the number of processors and M is the number of tasks. Since M = 4N, this simplifies to O(M log M) as sorting the tasks dominates the complexity. · **Space:** O(M), where M is the number of tasks. This is due to the space requirements of the sorting algorithm (Timsort) used by `Collections.sort` in Java.
**Pros:** Simple to conceive and implement.; Uses a common sorting pattern.
**Cons:** Produces a non-optimal, incorrect result.; The greedy choice is based on a flawed intuition.
### Explanation
This method is based on a simple greedy idea: give the 'easiest' work (shortest tasks) to the 'best' processors (earliest available). However, this intuition is flawed because it can lead to a situation where a late-starting processor is paired with very long tasks, creating a bottleneck and a high overall completion time.

Let's see why this fails with an example: `processorTime = [8, 10]`, `tasks` (sorted) = `[1, 2, 2, 3, 4, 5, 7, 8]`.
- Processor at time 8 gets tasks `{1, 2, 2, 3}`. Completion time: `8 + 3 = 11`.
- Processor at time 10 gets tasks `{4, 5, 7, 8}`. Completion time: `10 + 8 = 18`.
- The result is `max(11, 18) = 18`. The optimal answer is 16. This approach creates a bottleneck with the second processor.

```java
import java.util.List;
import java.util.Collections;

class Solution {
    public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) {
        int n = processorTime.size();
        
        Collections.sort(processorTime);
        Collections.sort(tasks);

        int maxCompletionTime = 0;

        for (int i = 0; i < n; i++) {
            // The longest task in the i-th group of 4 shortest tasks
            int currentMaxTask = tasks.get(4 * i + 3);
            int currentCompletionTime = processorTime.get(i) + currentMaxTask;
            if (currentCompletionTime > maxCompletionTime) {
                maxCompletionTime = currentCompletionTime;
            }
        }

        return maxCompletionTime;
    }
}
```
### Algorithm
- Sort the `processorTime` array in ascending order.
- Sort the `tasks` array in ascending order.
- Initialize a variable `maxCompletionTime` to 0.
- Iterate through the processors from `i = 0` to `n-1`.
- For the `i`-th processor, assign it the `i`-th group of 4 tasks from the sorted `tasks` array (i.e., tasks at indices `4*i` to `4*i+3`).
- The completion time for this processor is `processorTime[i] + tasks[4*i + 3]` (the longest task in its group).
- Update `maxCompletionTime = max(maxCompletionTime, currentCompletionTime)`.
- After the loop, return `maxCompletionTime`.

## Optimal Greedy Approach with Sorting
The key to minimizing the maximum completion time is to use a counter-intuitive greedy strategy. To balance the workload, the processors that become available earliest should be assigned the tasks that take the longest to complete. This pairing prevents any single processor from becoming a significant bottleneck. The late-starting processors are given the shortest tasks, as their start time already contributes heavily to their total completion time.
**Time:** O(M log M + N log N), where N is the number of processors and M is the number of tasks. Since M = 4N, this simplifies to O(M log M) as sorting the tasks is the most time-consuming step. · **Space:** O(M), where M is the number of tasks. This is due to the space requirements of the sorting algorithm (Timsort) used by `Collections.sort` in Java.
**Pros:** Correctly finds the minimum possible completion time.; Efficient, with complexity dominated by sorting.
**Cons:** The greedy choice might not be immediately obvious without understanding the underlying principle.
### Explanation
The problem is to minimize `max(processorTime[i] + max_task_for_processor_i)`. This is a classic scheduling problem where to minimize the maximum of sums, you should pair the smallest elements of one set with the largest elements of another.

Let's trace this with the example: `processorTime = [8, 10]`, `tasks = [2,2,3,1,8,7,4,5]`.
- Sorted `processorTime` (ascending): `[8, 10]`.
- Sorted `tasks` (descending): `[8, 7, 5, 4, 3, 2, 2, 1]`.
- Processor at time 8 gets tasks `{8, 7, 5, 4}`. Longest task is 8. Completion time: `8 + 8 = 16`.
- Processor at time 10 gets tasks `{3, 2, 2, 1}`. Longest task is 3. Completion time: `10 + 3 = 13`.
- The result is `max(16, 13) = 16`, which is the optimal solution.

```java
import java.util.List;
import java.util.Collections;

class Solution {
    public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) {
        int n = processorTime.size();
        
        // Sort processors by available time (ascending)
        Collections.sort(processorTime);
        
        // Sort tasks by duration (descending)
        Collections.sort(tasks, Collections.reverseOrder());

        int maxCompletionTime = 0;

        // Pair earliest processors with longest tasks
        for (int i = 0; i < n; i++) {
            // The i-th processor gets the i-th group of 4 tasks.
            // The longest task in this group is at index 4*i.
            int currentMaxTask = tasks.get(4 * i);
            int currentCompletionTime = processorTime.get(i) + currentMaxTask;
            
            if (currentCompletionTime > maxCompletionTime) {
                maxCompletionTime = currentCompletionTime;
            }
        }

        return maxCompletionTime;
    }
}
```
An alternative implementation could sort tasks in ascending order and then iterate through them from the end to achieve the same pairing.
### Algorithm
- Sort the `processorTime` array in ascending order.
- Sort the `tasks` array in **descending** order.
- Initialize a variable `maxCompletionTime` to 0.
- Iterate through the processors from `i = 0` to `n-1`.
- For the `i`-th processor (`processorTime[i]`), assign it the `i`-th group of four tasks from the descending sorted `tasks` list (i.e., tasks at indices `4*i` to `4*i+3`).
- The longest task in this group is `tasks[4*i]`.
- The completion time for this processor is `processorTime[i] + tasks[4*i]`.
- Update `maxCompletionTime = max(maxCompletionTime, currentCompletionTime)`.
- Return `maxCompletionTime`.

# Solutions
### Java

```java
class Solution {
public
  int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) {
    processorTime.sort((a, b)->a - b);
    tasks.sort((a, b)->a - b);
    int ans = 0, i = tasks.size() - 1;
    for (int t : processorTime) {
      ans = Math.max(ans, t + tasks.get(i));
      i -= 4;
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int: processorTime . sort() tasks . sort() ans = 0 i = len(tasks) - 1 for t in processorTime: ans = max(ans, t + tasks[i]) i -= 4 return ans

```

### CPP

```cpp
class Solution {
public:
  int minProcessingTime(vector<int> &processorTime, vector<int> &tasks) {
    sort(processorTime.begin(), processorTime.end());
    sort(tasks.begin(), tasks.end());
    int ans = 0, i = tasks.size() - 1;
    for (int t : processorTime) {
      ans = max(ans, t + tasks[i]);
      i -= 4;
    }
    return ans;
  }
};

```