Minimum Number of Workers

JavaView on GFG

Intuition

Minimum workers to finish all tasks given constraints on task/worker assignments. Bipartite matching or greedy.

Algorithm

1Sort tasks and workers. Greedy assignment: assign each task to any qualified worker. Binary search for optimal grouping.

Common Pitfalls

•Problem-specific constraints vary. Common approach: sort and greedy assign with feasibility check.

Minimum Number of Workers.java

Java

// Approach: Greedy assignment. Sort and pair workers to tasks in optimal order.
// Time: O(n log n) Space: O(1)
class Solution {
    public int minMen(int arr[]) {
        int n = arr.length;
        int[] maxReach = new int[n];
        for (int i = 0; i < n; i++)
            maxReach[i] = -1;

        for (int i = 0; i < n; i++) {
            if (arr[i] != -1) {
                int left = Math.max(0, i - arr[i]);
                int right = Math.min(n - 1, i + arr[i]);
                maxReach[left] = Math.max(maxReach[left], right);
            }
        }

        if (maxReach[0] == -1)
            return -1;

        int people = 0;
        int currEnd = 0;
        int farthest = 0;

        int i = 0;
        while (currEnd < n) {
            while (i <= currEnd && i < n) {
                farthest = Math.max(farthest, maxReach[i]);
                i++;
            }

            if (farthest < currEnd)
                return -1;
            people++;
            currEnd = farthest + 1;
        }

        return people;
    }
}

Was this solution helpful?