1834.single-threaded-cpu.md

1834. Single-Threaded CPU

Simulation + Heap

The problem can be solved by simulation and we have to handle the 3 major steps:

1. How to add tasks to the available tasks for CPU processing?
2. How to select the task with the smallest processing time?
3. How to process the task?

We can simulate the time elapse by starting the time from 0 and increment, we can sort the tasks by enqueue time so that we can enqueue task to available tasks for CPU processing 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!!

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

Give a time, there are some possible scenarios based on the conditions:

1. Whether CPU is idle or not.
2. Whether there are tasks to enqueue or not.
3. Whether there are tasks to process or not.

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----|

TODO: If CPU is idle, and the available tasks is empty (no task to process now), we can advance the current time to the next task's enqueue time. (B, and C as example)

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

If the all the tasks which enqueue time <= current time, 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.

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

After adding tasks to the available tasks, 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.

We can keep adding tasks to the available tasks or process the task with the smallest processing time until all the tasks are processed.

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

fun getOrder(originalTasks: Array<IntArray>): IntArray {
    // We build the tasks with original index
    val tasks = originalTasks.mapIndexed { index, task ->
        Task(task[0], task[1], index)
    }.toTypedArray()

    val n = tasks.size
    val order = mutableListOf<Int>()
    val availableTasks = PriorityQueue<Task>() { t1, t2 ->
        if (t1.processingTime == t2.processingTime) {
            t1.originalIndex - t2.originalIndex
        } else {
            t1.processingTime - t2.processingTime
        }
    }
    tasks.sortBy { it.enqueueTime }

    var i = 0
    var currentTime = 0
    while (i < n || availableTasks.isNotEmpty()) {
        // We add tasks to available tasks if the enqueue time <= current time
        while (i < n && tasks[i].enqueueTime <= currentTime) {
            availableTasks.add(tasks[i])
            i++
        }

        // If CPU is idle, and no task to process now, we can advance the current time to the next task's enqueue time
        if (i < n && availableTasks.isEmpty()) {
            currentTime = tasks[i].enqueueTime
            continue
        }
        
        // We process the task with the smallest processing time first, we can update
        // the process order and advance the current time
        if (availableTasks.isNotEmpty()) {
            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.