1834.single-threaded-cpu.md

1834. Single-Threaded CPU

Simulation + Heap

The problem can be solved by simulating the time elapse and handling the major steps:

• [Looping] when we have tasks to enqueue or to process:
  • [Enqueue tasks] Check if there is any task to enqueue at current time.
    • If yes, enqeue all tasks where enqueueTime <= currentTime.
    • If no, just skip this step.
  • [Process tasks] Check if there is any task to process at current time.
    • If yes, process the task with the smallest processing time.
    • If no, advance the current time to the next task's enqueue time.
• Return the order list.

We can sort the tasks by enqueue time so that we check if we can enqueue tasks where enqueueTime <= currentTime as time elapses. But before we sort the tasks, we need to keep the original index of the task so that we can return the order of the tasks. VERY IMPORTANT!! VERY IMPORTANT!! VERY IMPORTANT!!

• 索引在「排序後」就變了
• 索引在「排序後」就變了
• 索引在「排序後」就變了

很重要，所以說三次，但是答案要存原本的索引。因為我在這裡浪費了很多時間，因為我忘記了這一點。

After sorting, then we can start the simulation by looping until all the tasks are enqueued and processed.

Enqueue tasks

If the all the tasks which enqueueTime <= currentTime, we can add those tasks to the available tasks for CPU processing. (B, C as example) We can't add D because its enqueue time is 9, and the current time is 6.

                  t
time: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
...               |
            B-------->
            C---->|
                  |     D-->

Process tasks

After enqueuing all the tasks where enqueueTime <= currentTime, and the available tasks is empty (no task to process now), the CPU becomes idle,we can advance the current time to the next task's enqueue time. (B, and C as example)

time: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
      A----->        // Processed
            |-----|  // Idle
            t---->t' // Advance time
                  B-------->
                  C----->
                              D-->

If there are available tasks to process, we can process the task with the smallest processing time first, we can use a min heap to store the available tasks to find the task with the smallest processing time. We process the task by polling task from the min heap, advance the current time by the processing time of that task, and add the original index of the task to the order list.

data class Task(
    val enqueueTime: Int,
    val processingTime: Int,
    val originalIndex: Int
)

fun getOrder(originalTasks: Array<IntArray>): IntArray {
    val n = originaTasks.size
    // We build the tasks with original index
    val tasks = Array(n) {
        Task(originalTasks[it][0], originalTasks[it][1], it)
    }

    val order = mutableListOf<Int>()
    val availableTasks = PriorityQueue(compareBy<Task> { it.enqueueTime }.thenBy { it.originalIndex })
    tasks.sortBy { it.enqueueTime }

    var i = 0
    var currentTime = 1
    // [Looping] If there are tasks to enqueue or to process, we can continue the loop
    while (i < n || availableTasks.isNotEmpty()) {
        // Phase 1: Enqueue tasks
        // We add tasks to available tasks if the enqueue time <= current time
        while (i < n && tasks[i].enqueueTime <= currentTime) {
            availableTasks.add(tasks[i])
            i++
        }

        // Phase 2: Process tasks
        // If CPU is idle, and no task to process now, we can advance the current time to the next task's enqueue time
        if (availableTasks.isEmpty()) {
            if (i < n) {
                currentTime = tasks[i].enqueueTime
            }
        } else {
            val processTask = availableTasks.poll()
            order.add(processTask.originalIndex)
            currentTime += processTask.processingTime
        }
    }
    return order.toIntArray()
}

• Time Complexity: O(n log n), where n is the number of tasks. We need to sort the tasks by enqueue time, and we need to add tasks to the available tasks for CPU processing, which takes O(logN) time.
• Space Complexity: O(n), where n is the number of tasks. We need to store the tasks, available tasks, and order list.

Possible Scenarios

time
1, 2, 3, 4, 5, 6, ...
|0----|
   |1-----------|
      |2----|
         |3-|

1, 2, 3, 4, 5, 6, ...
|0-------------|
   |1-----|

1, 2, 3, 4, 5, 6, ...
|0-------|
|1----|
|2-|

1, 2, 3, 4, 5, 6, ...
|0-|     |1----|