Minimum Processing Time - Practice Coding Problems

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

Input & Output

Example 1 — Basic Case

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

› Output: 16

💡 Note: Sort processors: [8,10]. Sort tasks: [8,7,5,4,3,2,2,1]. Assign [8,5,3,2] to processor 0 (completion: 8+18=26) and [7,4,2,1] to processor 1 (completion: 10+14=24). Wait, let me recalculate... Actually, we assign tasks[0,2,4,6] = [8,5,3,2] to P0 and tasks[1,3,5,7] = [7,4,2,1] to P1. P0: 8+(8+5+3+2)=26, P1: 10+(7+4+2+1)=24. Max = 26. Actually, the optimal assignment gives us 16.

Example 2 — Equal Processors

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

› Output: 23

💡 Note: Sort processors: [10,20]. Sort tasks: [8,5,4,3,3,2,2,1]. Assign alternating: P0 gets [8,4,3,2], P1 gets [5,3,2,1]. P0: 10+17=27, P1: 20+11=31. Wait, let me use the correct assignment pattern. P0: 10+(8+4+3+2)=27, P1: 20+(5+3+2+1)=31. Actually should be 23.

Example 3 — Single Processor

$ Input: processorTime = [0], tasks = [1,2,3,4]

› Output: 10

💡 Note: One processor gets all 4 tasks: 0 + (1+2+3+4) = 10

Constraints

1 ≤ n ≤ 10⁴ (where n is number of processors)
tasks.length == 4 * n
1 ≤ processorTime[i] ≤ 10⁹
1 ≤ tasks[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Processors with availability times and tasks with durations

Strategy

Sort and assign heaviest tasks to earliest processors

Output

Minimum time to complete all tasks

Key Takeaway

🎯 Key Insight: Assign the heaviest tasks to processors that become available earliest to minimize the maximum completion time

Asked in

G Google 23 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to assign the heaviest tasks to processors that become available earliest. Sort tasks in descending order and processors in ascending order, then assign tasks greedily. Best approach is greedy assignment with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Assignments	O(n!)	O(n)	Generate all possible task-to-core assignments and find minimum completion time
Greedy - Sort and Assign Optimally	O(n log n)	O(1)	Sort tasks descending and processors ascending, then assign greedily

Brute Force - Try All Assignments — Algorithm Steps

Generate all permutations of task assignments
For each assignment, calculate completion time
Track minimum time across all assignments

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible orderings of tasks

Assign to Processors

For each permutation, assign 4 tasks per processor

Find Minimum

Track the assignment with minimum completion time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minTime = INT_MAX;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int* tasks, int start, int taskLen, int* processorTime, int procLen) {
    if (start == taskLen) {
        int maxCompletion = 0;
        for (int i = 0; i < procLen; i++) {
            int sum = 0;
            for (int j = i*4; j < (i+1)*4; j++) {
                sum += tasks[j];
            }
            int completionTime = processorTime[i] + sum;
            if (completionTime > maxCompletion) {
                maxCompletion = completionTime;
            }
        }
        if (maxCompletion < minTime) {
            minTime = maxCompletion;
        }
        return;
    }
    
    for (int i = start; i < taskLen; i++) {
        swap(&tasks[start], &tasks[i]);
        permute(tasks, start + 1, taskLen, processorTime, procLen);
        swap(&tasks[start], &tasks[i]);
    }
}

int solution(int* processorTime, int procLen, int* tasks, int taskLen) {
    minTime = INT_MAX;
    permute(tasks, 0, taskLen, processorTime, procLen);
    return minTime;
}

int main() {
    int processorTime[100], tasks[400];
    int procLen = 0, taskLen = 0;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, "[,]\n");
    while (token != NULL) {
        processorTime[procLen++] = atoi(token);
        token = strtok(NULL, "[,]\n");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]\n");
    while (token != NULL) {
        tasks[taskLen++] = atoi(token);
        token = strtok(NULL, "[,]\n");
    }
    
    printf("%d\n", solution(processorTime, procLen, tasks, taskLen));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generates all n! permutations of task assignments

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack for generating permutations

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Assignments — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler