java - Given tasks and programmers solve the tasks in less time - Stack Overflow

I have a list of tasks of size n and the time taken to process is represented as tasks[i], where i is index for the task.

Processing Step: These tasks should be processed sequentially from i = 0 to i = n-1, one after the other.

Now there is another list of programmers of size m, who can work on the tasks for a specified duration represented by programmers[i], where i is the index.

A task is said to be completed if its value is 0, otherwise it is a pending task.

So if there are some tasks pending by end of above mentioned processing step, processing should start again from i = 0 to i = n-1

If all tasks are finished, then we can load the tasks back and start the processing from beginning.

I want to collect how many tasks are still pending after each programmer works for their specified duration.

Here is an example:

Example 1

n=5, tasks = [2, 4, 5, 1, 1] m=5, programmers = [1, 5, 1, 5, 2]

Programmer	Tasks	Pending tasks
1	[1, 4, 5, 1, 1]	The first task is partially processed, total pending tasks = 5
2	[0, 0, 5, 1, 1]	The first two tasks are fully processed, total pending tasks = 3
3	[0, 0, 4, 1, 1]	The third task is partially processed, total pending tasks = 3
4	[0, 0, 0, 0, 1]	The third and fourth tasks are fully processed, total pending tasks = 1
5	[0, 0, 0, 0, 0]	The last task is fully processed, total pending tasks = 0

I have a list of tasks of size n and the time taken to process is represented as tasks[i], where i is index for the task.

Processing Step: These tasks should be processed sequentially from i = 0 to i = n-1, one after the other.

Now there is another list of programmers of size m, who can work on the tasks for a specified duration represented by programmers[i], where i is the index.

A task is said to be completed if its value is 0, otherwise it is a pending task.

So if there are some tasks pending by end of above mentioned processing step, processing should start again from i = 0 to i = n-1

If all tasks are finished, then we can load the tasks back and start the processing from beginning.

I want to collect how many tasks are still pending after each programmer works for their specified duration.

Here is an example:

Example 1

n=5, tasks = [2, 4, 5, 1, 1] m=5, programmers = [1, 5, 1, 5, 2]

Programmer	Tasks	Pending tasks
1	[1, 4, 5, 1, 1]	The first task is partially processed, total pending tasks = 5
2	[0, 0, 5, 1, 1]	The first two tasks are fully processed, total pending tasks = 3
3	[0, 0, 4, 1, 1]	The third task is partially processed, total pending tasks = 3
4	[0, 0, 0, 0, 1]	The third and fourth tasks are fully processed, total pending tasks = 1
5	[0, 0, 0, 0, 0]	The last task is fully processed, total pending tasks = 0

Hence, the number of pending tasks = [5, 3, 3, 1, 0]

Example 2

tasks = [1, 2, 4, 1, 2] programmers = [3, 10, 1, 1, 1]

Programmer	Tasks	Pending tasks
1	[0, 0, 4, 1, 2]	The first and second tasks are fully processed, total pending tasks = 3
2	[0, 0, 0, 0, 0]	All tasks are fully processed, total pending tasks = 0 (Pending is 0 so load back all tasks [1,2,4,1,2])
3	[0, 2, 4, 1, 2]	The first task is fully processed, total pending tasks = 4
4	[0, 1, 4, 1, 2]	The second task is partially processed, total pending tasks = 4
5	[0, 0, 3, 1, 2]	The second task is fully processed, total pending tasks = 3

Output = [3,0,4,4,3]

Example 3

tasks = [1, 4, 4] programmers = [9, 1, 4]

Output = [0, 2, 1]

Here is my code that runs in O(m*n) time:

import java.util.*;

public class Main {

    public static List<Integer> getPendingTasks(List<Integer> tasks, List<Integer> programmers) {
        List<Integer> pendingTasks = new ArrayList<>();
        List<Integer> originalTasks = new ArrayList<>(tasks); // Save original tasks for reloading
        int n = tasks.size();
        
        for (int programmer : programmers) {
            int timeRemaining = programmer;
            for (int i = 0; i < n && timeRemaining > 0; i++) {
                if (tasks.get(i) > 0) {
                    if (tasks.get(i) <= timeRemaining) {
                        timeRemaining -= tasks.get(i);
                        tasks.set(i, 0);
                    } else {
                        tasks.set(i, tasks.get(i) - timeRemaining);
                        timeRemaining = 0;
                    }
                }
            }

            // Count pending tasks
            int pending = 0;
            for (int task : tasks) {
                if (task > 0) {
                    pending++;
                }
            }

            pendingTasks.add(pending);

            // Reload tasks if all are completed
            if (pending == 0) {
                tasks = new ArrayList<>(originalTasks);
            }
        }

        return pendingTasks;
    }

    public static void main(String[] args) {
        // Example 1
        List<Integer> tasks1 = Arrays.asList(2, 4, 5, 1, 1);
        List<Integer> programmers1 = Arrays.asList(1, 5, 1, 5, 2);
        System.out.println("Output: " + getPendingTasks(tasks1, programmers1)); // Output: [5, 3, 3, 1, 0]

        // Example 2
        List<Integer> tasks2 = Arrays.asList(1, 2, 4, 1, 2);
        List<Integer> programmers2 = Arrays.asList(3, 10, 1, 1, 1);
        System.out.println("Output: " + getPendingTasks(tasks2, programmers2)); // Output: [3, 0, 4, 4, 3]

        // Example 3
        List<Integer> tasks3 = Arrays.asList(1, 4, 4);
        List<Integer> programmers3 = Arrays.asList(9, 1, 4);
        System.out.println("Output: " + getPendingTasks(tasks3, programmers3)); // Output: [0, 2, 1]
    }
}

I also tried using PriorityQueue to process only pending tasks:

import java.util.*;

class Main {

    public static List<Integer> getPendingTasks(List<Integer> tasks, List<Integer> programmer) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> pending = new PriorityQueue<>();
        int n = tasks.size();
        List<Integer> originalTasks = new ArrayList<>(tasks);

        // Initialize set with all tasks
        for (int i = 0; i < n; i++) {
            pending.add(i);
        }
        Queue<Integer> q = new PriorityQueue<>(pending);
        
        // Process each item
        for (int p : programmer) {
            int timeAvailable = p;

            // Process only unprocessed tasks
            List<Integer> balancedTask = new ArrayList<>();
            
            while (!q.isEmpty()) {
                int i = q.poll();
                if (tasks.get(i) <= timeAvailable) {
                    timeAvailable -= tasks.get(i);
                    // Task fully processed
                } else {
                    tasks.set(i, tasks.get(i) - timeAvailable); // Partially processed
                    timeAvailable = 0; // time exhausted
                    balancedTask.add(i);
                }
            }
            q.addAll(balancedTask);
            result.add(q.size());
            if(q.size() ==0) {
                tasks = originalTasks;
                q= pending;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(getPendingTasks(Arrays.asList(2, 4, 5, 1, 1), Arrays.asList(1, 5, 1, 5, 2))); 
        // Expected: [5, 3, 3, 1, 0]
        
        System.out.println(getPendingTasks(Arrays.asList(1, 2, 4, 1, 2), Arrays.asList(3, 10, 1, 1, 1))); 
        // Expected: [3, 0, 4, 4, 3]
        
        System.out.println(getPendingTasks(Arrays.asList(1, 4, 4), Arrays.asList(9, 1, 4))); 
        // Expected: [0, 2, 1]
    }
}

But above code also runs in O(n*m*log(m)) time complexity

Constraints:

n and m in range 1 to 2 * 10^5
each item in input lists is 1 to 10^9

I want to know how to solve this in less time complexity

• java
• algorithm
• time-complexity

Share Improve this question Follow edited Jan 23 at 3:52 Rusty 15711 silver badge1010 bronze badges asked Jan 22 at 21:09 CodeCrusaderCodeCrusader 45922 silver badges1212 bronze badges 5

• ", if all tasks are finished in middle of some programmer" I guess you mean "if all tasks are finished, while some programmer is in the middle of working on a task" How can this ever happen? If some programmer is working on a task then that task is not finished. – ravenspoint Commented Jan 22 at 22:06
• Please edit your question so it makes sense. If you cannot explain the problem clearly, then how do you expect to be able to write code that solves the problem correctly. Understanding must come before coding. – ravenspoint Commented Jan 22 at 22:16
• Looking at the problem statement, it's obvious that you cannot do better than O(m), because you need to output a list of size m. If O(mn) is too slow, you can try to come up with an algorithm of complexity O(mlog(n)). Basically you need to speed up each iteration of the loop over the programmers. Hint: you need to do some precomputation in the beginning. Hope this helps. – user20488960 Commented Jan 22 at 23:11
• @CodeCrusader Asking here is supposed to ask for specific details, like certain things you can't figure out. It's not normally a forum for designing things. There are other places for that. – Ted Lyngmo Commented Jan 22 at 23:25
• At the very least fix this obvious nonsense " if all tasks are finished in middle of some programmer" – ravenspoint Commented Jan 23 at 0:46

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

We can compute the prefix sum array for the task durations, then binary search on each iteration for the first point where the total task duration is more than the amount of work the current programmer can do (for a time complexity of O(m log n)).

public static List<Integer> getPendingTasks(List<Integer> tasks, List<Integer> programmers) {
    var res = new ArrayList<Integer>(programmers.size());
    var sum = new long[tasks.size() + 1];
    for (int i = 1; i <= tasks.size(); i++) sum[i] = sum[i - 1] + tasks.get(i - 1);
    int prev = 0;
    long extra = 0;
    for (int work : programmers) {
        if (work >= sum[tasks.size()] - sum[prev] + extra) {
            res.add(0);
            extra = prev = 0;
            continue;
        }
        int low = prev, high = tasks.size();
        while (low <= high) {
            int mid = low + high >>> 1;
            if (sum[mid] - sum[prev] + extra > work) high = mid - 1;
            else low = mid + 1;
        }
        extra = sum[low] - sum[prev] + extra - work;
        prev = low;
        res.add(tasks.size() - low + (extra > 0 ? 1 : 0));
    }
    return res;
}