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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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 <= 10^5
  • 0 <= processorTime[i] <= 10^9
  • 1 <= tasks[i] <= 10^9
  • tasks.length == 4 * n

Solution

Method 1 – Greedy Assignment (Sort and Group)

Intuition

Assign the largest tasks to the earliest available processors. Sort both arrays, assign every 4 tasks to each processor, and compute the max finish time for each processor.

Approach

  1. Sort processorTime and tasks.
  2. For each processor, assign 4 largest remaining tasks.
  3. For each processor, compute max(processorTime[i] + task[j]) for its 4 tasks.
  4. Return the maximum among all processors.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <algorithm>
class Solution {
public:
    int minProcessingTime(std::vector<int>& processorTime, std::vector<int>& tasks) {
        std::sort(processorTime.begin(), processorTime.end());
        std::sort(tasks.rbegin(), tasks.rend());
        int n = processorTime.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            int mx = 0;
            for (int j = 0; j < 4; ++j) {
                mx = std::max(mx, processorTime[i]+tasks[i*4+j]);
            }
            res = std::max(res, mx);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import "sort"
func minProcessingTime(processorTime []int, tasks []int) int {
    sort.Ints(processorTime)
    sort.Sort(sort.Reverse(sort.IntSlice(tasks)))
    n, res := len(processorTime), 0
    for i := 0; i < n; i++ {
        mx := 0
        for j := 0; j < 4; j++ {
            if processorTime[i]+tasks[i*4+j] > mx { mx = processorTime[i]+tasks[i*4+j] }
        }
        if mx > res { res = mx }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import java.util.*;
class Solution {
    public int minProcessingTime(int[] processorTime, int[] tasks) {
        Arrays.sort(processorTime);
        Arrays.sort(tasks);
        int n = processorTime.length, res = 0;
        for (int i = 0; i < n; i++) {
            int mx = 0;
            for (int j = 0; j < 4; j++) {
                mx = Math.max(mx, processorTime[i]+tasks[tasks.length-1-(i*4+j)]);
            }
            res = Math.max(res, mx);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    fun minProcessingTime(processorTime: IntArray, tasks: IntArray): Int {
        processorTime.sort()
        tasks.sortDescending()
        var res = 0
        for (i in processorTime.indices) {
            var mx = 0
            for (j in 0..3) {
                mx = maxOf(mx, processorTime[i]+tasks[i*4+j])
            }
            res = maxOf(res, mx)
        }
        return res
    }
}
1
2
3
4
5
6
7
8
9
class Solution:
    def minProcessingTime(self, processorTime: list[int], tasks: list[int]) -> int:
        processorTime.sort()
        tasks.sort(reverse=True)
        n, res = len(processorTime), 0
        for i in range(n):
            mx = max(processorTime[i]+tasks[i*4+j] for j in range(4))
            res = max(res, mx)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn min_processing_time(mut processor_time: Vec<i32>, mut tasks: Vec<i32>) -> i32 {
        processor_time.sort();
        tasks.sort_by(|a,b|b.cmp(a));
        let n = processor_time.len();
        let mut res = 0;
        for i in 0..n {
            let mx = (0..4).map(|j| processor_time[i]+tasks[i*4+j]).max().unwrap();
            res = res.max(mx);
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    minProcessingTime(processorTime: number[], tasks: number[]): number {
        processorTime.sort((a,b)=>a-b);
        tasks.sort((a,b)=>b-a);
        let n = processorTime.length, res = 0;
        for (let i = 0; i < n; i++) {
            let mx = 0;
            for (let j = 0; j < 4; j++) {
                mx = Math.max(mx, processorTime[i]+tasks[i*4+j]);
            }
            res = Math.max(res, mx);
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + m log m) — Sort both arrays, then one pass.
  • 🧺 Space complexity: O(1) — In-place sort.