1834. Single-Threaded CPU

這題其實有點算實作題, 題目有提到

the CPU will choose the one with the shortest processing time. 
=> pq (small processingTimei, smallest index)

所以要用 pq, 因為要對 time, index 做排序, 所以做一個 class 出來存會是比較漂亮的作法,

Queue<Task> queue = new PriorityQueue<>((a,b) -> {
            return a.processingTime == b.processingTime ? a.index - b.index : a.processingTime - b.processingTime;
        });

因為是照時間順序來放入 pq, 所以當然開始時間要先排序

Arrays.sort(jobs, (a,b) -> a.enqueueTime - b.enqueueTime);

比較不好設計的部分是, 如何按照 啟動時間 入 pq 呢？

from the name enqueueTime => hint us can add to queue

重點要有個 curTime 來記錄目前時間到哪裡了, pq 是空的時候, 會給予初值（第一個job 的起始時間）

其他 pq 有元素時, 當然就是更新結果和更新 curTime (加上 processingTime, 因為這是一個 single thread 的 CPU, 一次做一件事)

from array to queue

也維持了一個 runIdx 來讀下個 job, 條件是 起始時間 <= curTime

while()...這裏

如此就可以把符合起始時間 的job 入 pq

        int[] order = new int[n];
        int orderIdx = 0;
        int runIdx = 0;
        int curTime = 0;
        while (orderIdx < n) {
            
            while (runIdx < n && jobs[runIdx].enqueueTime <= curTime) {
                queue.offer(jobs[runIdx]);
                runIdx++;
            }
            // when no data in queue, curTime needs to refresh
            if (queue.isEmpty()) {
                curTime = jobs[runIdx].enqueueTime;
            } else {
                Task cur = queue.poll();
                order[orderIdx++] = cur.index;
                curTime += cur.processingTime;
            }
        }
        return order;

T: O(nlogn)
S: O(n)

class Solution {
    class Task {
        int index;
        int enqueueTime;
        int processingTime;
        Task(int index,
             int enqueueTime,
             int processingTime) {
            
            this.index = index;
            this.enqueueTime = enqueueTime;
            this.processingTime = processingTime;
        }
    }
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        Task[] jobs = new Task[n]; 
        for (int i = 0; i < n; i++) {
            jobs[i] = new Task(i, tasks[i][0], tasks[i][1]);
        }
        Arrays.sort(jobs, (a,b) -> a.enqueueTime - b.enqueueTime);
        
        Queue<Task> queue = new PriorityQueue<>((a,b) -> {
            return a.processingTime == b.processingTime ? a.index - b.index : a.processingTime - b.processingTime;
        });
        
        int[] order = new int[n];
        int orderIdx = 0;
        int runIdx = 0;
        int curTime = 0;
        while (orderIdx < n) {
            
            while (runIdx < n && jobs[runIdx].enqueueTime <= curTime) {
                queue.offer(jobs[runIdx]);
                runIdx++;
            }
            // when no data in queue, curTime needs to refresh
            if (queue.isEmpty()) {
                curTime = jobs[runIdx].enqueueTime;
            } else {
                Task cur = queue.poll();
                order[orderIdx++] = cur.index;
                curTime += cur.processingTime;
            }
        }
        return order;
    }
}

/*
tasks[i] = [enqueueTimei, processingTimei]

ith task
process at enqueueTimei, needs processingTimei


the CPU will choose the one with the shortest processing time. 
=> pq (small processingTimei, smallest index)

finished entire task


Return the order in which the CPU will process the tasks. (index)


[[1,2],[2,4],[3,2],[4,1]]


1. build task class
2. define pq

curTime = 0;
3. while (orderId < n) {
    while (runId < n && eTime <= curTime) {
        add to heap
        runId++
    }
    if (heap is empty) {
        init curTime = task[runId].eTime
    }
    
    heap pop, get cur task
    add to result[orderId++]
    curTime += cur task.proTime
    
}

T: O(nlogn)
S: O(n)
*/