2279. Maximum Bags With Full Capacity of Rocks

Hello, reader 👋🏽 ! Welcome to day 89 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1834. Single-Threaded CPU.

🤔 Problem Statement

You are given n tasks labelled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the ith task will be available to process at enqueueTimei and will take processingTimei to finish processing.
You have a single-threaded CPU that can process at most one task at a time and will act in the following way:
- If the CPU is idle and there are no available tasks to process, the CPU remains idle.
- If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
- Once a task is started, the CPU will process the entire task without stopping.
- The CPU can finish a task and then start a new one instantly.
Return the order in which the CPU will process the tasks.
E.g.:
- tasks = [[1,2],[2,4],[3,2],[4,1]] => [0,2,3,1]
- tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] => [4,3,2,0,1]

💬 Thought Process - Priority Queue

We have to start processing the tasks that have the lowest enqueue time. To find the task(s), we can sort the array.
But if we sort the array, we will lose the original ordering of the tasks, hence will be unable to choose between tasks that could have the same processing time.
To work around this, we'll have to create a new array with every task having the following information: [enqueueTime, processingTime, index].
Then, we can sort the array based on the enqueue time -- tasksByEnqueue.
Now, we will have to form the ordering of these tasks. We will have to iterate every task that was sorted by enqueue time.
We'll also have to hold a currTime iterator that keeps track of the current ongoing time to decide if we can schedule new task(s) or not.
Initially, the currTime will be equal to the smallest enqueueTime of the task. Hence from the sorted array, the currTime would be equal to tasksByEnqueue[0][0].
Then we will iterate through the tasksByEnqueue and use a priority queue to decide the smallest tasks by processing time or index (if the processing time is the same).
We'll also use an index pointer in order to keep track of the next task to be processed from the sorted list of tasks - tasksByEnqueue.
In every iteration, all tasks whose enqueue time is lesser or equal to the current time will be scheduled and added to the priority queue.
Each time, if there are any tasks scheduled, i.e. the priority queue is not empty, the first task would be polled and processed.
- The polled task's index will be added to the final answer.
- Then we'll update the currTime and add the processingTime of the polled task -- currTime += processingTime.
But, if there are no tasks scheduled, then we'll update the currTime to the next task with the smallest enqueueTime. Hence currTime = tasksByEnqueue[index][0].
This loop would be repeated until all the tasks are processed.

👩🏽‍💻 Solution - Priority Queue

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;

        /*
            We cannot sort the array as original ordering is required
            Create a new array -- tasksByEnqueue with 
            tasksByEnqueue[i] = [enqueueTime, processingTime, index]
        */
        int[][] tasksByEnqueue = new int[n][3];
        for(int i = 0; i<n; i++) {
            int[] task = tasks[i];

            tasksByEnqueue[i] = new int[] {
                task[0], task[1], i
            };
        }

        // Sort tasksByEnqueue by enqueueTime
        Arrays.sort(tasksByEnqueue, (a,b) -> a[0] - b[0]);

        // To keep track of all the scheduled tasks 
        // such that enqueueTime <= currTime
        PriorityQueue<int[]> scheduledTasks = new PriorityQueue<int[]>
        (
            (a,b) -> a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]
        );

        // index -- represents index of the next smallest task
        // currTime -- current CPU time
        // order -- represents order of tasks processed
        int index = 0, currTime = tasksByEnqueue[index][0];

        int[] order = new int[n];
        int orderIndex = 0;

        while(orderIndex < n) {
            // Schedule all tasks with enqueueTime <= currTime
            while(index < n && tasksByEnqueue[index][0] <= currTime) {
                scheduledTasks.add(tasksByEnqueue[index]);
                index++;
            }

            // If any scheduled task, poll and process it
            // add the polled task index to the order 
            // update currTime with the polled task's processTime
            if(!scheduledTasks.isEmpty()) {
                int[] currTask = scheduledTasks.poll();
                int processTime = currTask[1];
                int taskIndex = currTask[2];
                order[orderIndex++] = taskIndex;
                currTime += processTime;
                continue;
            }
            // If no task scheduled, update currTime to task with
            // next smallest enqueueTime
            else {
                currTime = tasksByEnqueue[index][0];
            }
        }

        return order;
    }
}

Time Complexity: O(n * log n)
    - It would roughly take: O(n + n*log n + n*log n)
        - n => create tasksByEnqueue -- list of tasks
        - n*log n => sort the tasksByEnqueue
        - n*log n => poll, add n tasks to priority queue
Space Complexity: O(n)
    - Maintain a heap and array of tasksByEnqueue

You can find the link to all the solutions on GitHub for this question here: 2279. Maximum Bags With Full Capacity of Rocks.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

1834. Single-Threaded CPU

Table of contents

🤔 Problem Statement

💬 Thought Process - Priority Queue

👩🏽‍💻 Solution - Priority Queue

Conclusion