Single-Threaded CPU

class Solution {
public:
    vector<int> taskExecutionOrder(vector<vector<int>>& tasks) {
        // Min-heap to determine the next task to process based on conditions.
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
        // Enhance task information by adding their original indices.
        vector<array<int, 3>> enhancedTasks;
        for (int i = 0; i < tasks.size(); ++i) {
            enhancedTasks.push_back({tasks[i][0], tasks[i][1], i});
        }
    
        sort(enhancedTasks.begin(), enhancedTasks.end());
        vector<int> executionOrder;
    
        long long currentTime = 0;
        int idx = 0;
    
        // Process until all tasks are handled.
        while (idx < tasks.size() || !pq.empty()) {
            // Sync currentTime if no tasks are available in queue.
            if (pq.empty() && currentTime < enhancedTasks[idx][0]) {
                currentTime = enhancedTasks[idx][0];
            }
    
            // Enqueue tasks available by current time into the heap.
            while (idx < enhancedTasks.size() && currentTime >= enhancedTasks[idx][0]) {
                pq.push({enhancedTasks[idx][1], enhancedTasks[idx][2]});
                ++idx;
            }
    
            auto [timeToProcess, taskIdx] = pq.top();
            pq.pop();
    
            // Advance time and record task completion.
            currentTime += timeToProcess;
            executionOrder.push_back(taskIdx);
        }
    
        return executionOrder;
    }
};

The provided C++ solution is designed for scheduling tasks on a single-threaded CPU. The main goal is to determine the order of task execution using a priority queue. Here’s a breakdown of the process:

• Start by storing tasks in an enhanced format that includes the original index of each task. This is critical for later identifying the order in which tasks are executed.

• Use a priority queue (min-heap) to manage tasks based on their processing time and the order they need to be addressed. The queue will ensure the task with the smallest processing time available at the current time is processed next.

• Sort the enhanced task list based on the start time. This prepares the list for sequential processing, ensuring tasks are considered in the correct order of when they should be started.

• Implement a loop that continues until all tasks are handled. The approach includes dynamically adjusting the currentTime to reflect the simulation of time passage as tasks are executed.

• Within the loop, tasks are added to the priority queue if their starting time is less than or equal to the currentTime. This maintains the queue with currently available tasks.

• Execute the task at the top of the priority queue, which will have the minimal processing time among the available tasks. Then update the currentTime by adding the task's processing duration, simulating the task's completion.

• After processing the task, record its original index. This array will represent the order of task execution, which is the desired output.

• Finally, return the execution order after all tasks have been processed. This result allows one to understand how the CPU would handle the tasks based on their arrival and processing times.

This method ensures efficient handling of task scheduling, simulating a real-time environment for task execution on a single-threaded CPU using data structure and algorithmic concepts. The solution carefully balances task arrival time and processing time to optimize the CPU's workflow.

class Scheduler {
    public int[] processTasks(int[][] inputs) {
            
        // Create a priority queue with custom comparator.
        PriorityQueue<int[]> scheduleQueue = new PriorityQueue<>((task1, task2) -> {
            if (task1[1] != task2[1]) return task1[1] - task2[1];
            else return task1[2] - task2[2];
        });
            
        // Array to hold tasks details along with their original indices.
        int[][] taskDetails = new int[inputs.length][3];
        for (int i = 0; i < inputs.length; i++) {
            taskDetails[i][0] = inputs[i][0];
            taskDetails[i][1] = inputs[i][1];
            taskDetails[i][2] = i;
        }
            
        // Sort tasks by their enqueue time.
        Arrays.sort(taskDetails, (task1, task2) -> Integer.compare(task1[0], task2[0]));
        int[] taskExecutionOrder = new int[inputs.length];
            
        long currentTime = 0;
        int idx = 0;
        int resultIndex = 0;
            
        // Simulation loop.
        while (idx < inputs.length || !scheduleQueue.isEmpty()) {
            // If queue is empty, jump time to next available task's starting time.
            if (scheduleQueue.isEmpty() && currentTime < taskDetails[idx][0]) {
                currentTime = taskDetails[idx][0];
            }
                
            // Add tasks to the queue which can start at current time.
            while (idx < inputs.length && currentTime >= taskDetails[idx][0]) {
                scheduleQueue.add(taskDetails[idx]);
                idx++;
            }
                
            int processingTime = scheduleQueue.peek()[1];
            int originalIndex = scheduleQueue.peek()[2];
            scheduleQueue.remove();
                
            // Process the task and advance the time.
            currentTime += processingTime; 
            taskExecutionOrder[resultIndex++] = originalIndex;
        }
            
        return taskExecutionOrder;
    }
}

This solution involves a simulation of how a single-threaded CPU schedules tasks. The implementation is carried out in Java using a class named Scheduler. The method processTasks in this class is designed to take an array of tasks where each task is represented as an array of two integers, [enqueueTime, processingTime]. The method returns the order in which the tasks are executed.

In the code:

• A PriorityQueue is used to manage tasks based on their processing time, and, if equal, by their original indices.
• An array, taskDetails, expands the input to include task indices, helping track the order tasks are added to the queue.
• Tasks are initially sorted by their enqueue time to simulate their arrival.
• Using variables like currentTime, idx for indexing through the tasks, and resultIndex for building the output, the method simulates the CPU processing tackling several conditions:
  • If the queue is empty but it's still not time for the next task, the scheduler jumps in time to the next task's enqueue time.
  • It queues tasks that are ready to be processed based on the current time.
  • It then processes a task, removing it from the queue and appending its index to the result array.
  • The current time is incremented by the task's processing time.

Finally, the method returns the execution order of the tasks as an array of indices referring to their original order in the input. This simulation effectively imitates a CPU scheduler using a single thread, emphasizing task prioritization based on quick execution time and earliest arrival.

class Solution:
    def fetchOrder(self, activities: List[List[int]]) -> List[int]:
        # Priority for tasks in terms of processing time and index.
        active_list: List[Tuple[int, int]] = []
        execution_order: List[int] = []
    
        # Prepare tasks with their start time, duration, and original index.
        sorted_activities = [(start, duration, pos) for pos, (start, duration) in enumerate(activities)]
        sorted_activities.sort()
    
        time_now = 0
        index = 0
    
        # Process until all tasks are handled.
        while index < len(activities) or active_list:
            # Adjust current time if needed when no active tasks are available.
            if not active_list and time_now < sorted_activities[index][0]:
                time_now = sorted_activities[index][0]
    
            # Load all available tasks into the heap.
            while index < len(sorted_activities) and time_now >= sorted_activities[index][0]:
                _, duration, orig_index = sorted_activities[index]
                heapq.heappush(active_list, (duration, orig_index))
                index += 1
    
            duration, idx = heapq.heappop(active_list)
    
            # Process the next task and move the time forward.
            time_now += duration
            execution_order.append(idx)
    
        return execution_order

This Python solution is designed to simulate the operation of a single-threaded CPU that processes a list of tasks. The primary goal is to determine the order in which tasks are processed based on their availability and duration. The tasks are represented as a list of lists, where each sublist contains two integers: the start time and the duration of the task.

The function fetchOrder inside the Solution class returns the order of task indices after processing:

• Start by storing each task with an associated position index (pos) and sort these tasks based on start times.
• Use a heap (priority queue) active_list to manage tasks based on their durations once they become available.
• Iterate through sorted tasks and push available tasks into the heap based on the current time time_now. Only tasks that start at or before time_now are considered.
• Pop tasks from the heap (selecting the one with the shortest duration next) and simulate the processing by advancing time_now by the duration of the task.
• Continue processing until all tasks from the list and all tasks in the heap are handled.
• The resultant list execution_order contains the indices of the tasks in the order they were processed.

This algorithm effectively schedules tasks, ensuring that the CPU processes the next available task with the shortest duration, thereby simulating a realistic scheduling scenario for a single-threaded CPU.