[Java]LeetCode 1834. Single-Threaded CPU

LeetCode 1834. Single-Threaded CPU - Java

 

문  제 : 

싱글 스레드로 동작하는(한 번에 하나의 작업을 하는) CPU가 있다.

해야 할 작업 목록이 주어 졌을 때 CPU가 일을 처리하는 순서를 구해라.

※ CPU가 작업을 고르는 기준

     1. 시작 시간이 되어야함

     2. 시작 할 수 있는 작업이 여러 개 있다면, 가장 시간이 적게 걸리는 작업을 먼저 함.

     3. 걸리는 시간이 똑같다면, 시작시간이 먼저인 것을 먼저 함.

 

---

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]

Explanation: The events go as follows:
- At time = 1, task 0 is available to process. Available tasks = {0}.
     - Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
     - Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks =          {1}. - 
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

---

해  결 : 

(1) 시간을 기준으로 오름차순으로 정렬한 후, 작업을 시작한다.

(2) 작업이 끝나면 그 작업을 하는데에 걸린 시간을 총 시간에 더해준다. + 마친 작업 목록에 추가한다.

(3) 총 시간보다 시작 시간이 작은 작업들을 작업 큐에 추가 해준다.

(4) 만약 (3)의 과정이 생략 되었다면 큐에 다음 작업을 추가해준다.

(5) (2)~(4) 과정을 작업을 모두 마칠 때까지 반복한다.

 

---

작업 목록을 관리할 Class와 Priority Queue 선언.

   - Priority Queue의 기준은 작업의 수행시간이 낮을수록, 같다면 index가 낮은 작업을 우선순위로 한다.

PriorityQueue<Task> taskQueue = new PriorityQueue<>(); // 우선순위 큐 선언

class Task implements Comparable<Task> {
    public int index;
    public int start;
    public int processing;

    public Task(int i, int s, int p) {
        index = i;
        start = s;
        processing = p;
    }
    @Override
    public int compareTo(Task task) {
        if (this.processing > task.processing) // 오름차 순
            return 1;
        else if (this.processing < task.processing)
            return -1;
        else { // processing 같다면 인덱스 오름차 순
            if(this.index > task.index) return 1;
            else return -1;
        }
    }
}

---

작업 목록을 정렬해 관리할 ArrayList 선언

ArrayList에 작업들 삽입

ArrayList 정렬

    - ArrayList의 정렬 기준은 작업의 시작시간을 기준으로 오름차순으로 정렬한다.

      만약 시작시간이 같다면, 걸리는 시간을 기준으로 오름차순으로 정렬한다.

ArrayList<Task> task = new ArrayList<>();

for(int i=0; i < tasks.length; i++){
    Task temp = new Task(i, tasks[i][0], tasks[i][1]);
    task.add(temp);
}

Collections.sort(task, (o1, o2) -> {
    return o1.start!=o2.start ? o1.start-o2.start : o1.processing-o2.processing; // 시작 시간, 작업 시간 기준  오름차순 정렬
});

---

Task Queue에 첫 번째 작업을 추가해주고 총 시간 변수 (endTime) 을 지정해준다.

Task Queue에서 작업을 하나 씩 골라 작업을 진행한다.

진행하면서 걸린 시간을 총 시간에 더해주고, 그 시간에 시작한 작업들을 또 Task Queue에 추가해준다.

만약, 작업을 전부 완료하지 않았음에도 Task Queue가 비어지게 되면, 다음 작업을 바로 추가해준다.

taskQueue.add(task.get(k++)); // 첫 번째 작업
endTime += task.get(0).start;

while(true) {
    currentTask = taskQueue.poll(); // 방금 다 한 작업
    endTime += currentTask.processing; // 끝났을 때의 시간
    result[r++] = currentTask.index; // 다 한 작업 결과에 추가

    if(r == task.size()) return result; // 작업을 다 추가 했다면 종료

    if(k < task.size()){
        while(endTime >= task.get(k).start){ // 끝났을 때의 시간보다 start 가 작은 애들 전부 queue에 넣어줌
            taskQueue.add(task.get(k));
            k++;
            if(k > task.size()-1) break;
        }
    } 
    if(taskQueue.isEmpty() && k < task.size()){ // 작업이 남았는데 start시간이 늦어서 큐에 아무것도 못 들어갔을 때
        taskQueue.add(task.get(k));
        endTime = task.get(k).start;
        k++;
    }
}

---

결   과 :

class Solution {
    public int[] getOrder(int[][] tasks) {
        int result[] = new int[tasks.length];
        int r = 0;
        int k = 0;
        int endTime = 0;
        Task currentTask;
        ArrayList<Task> task = new ArrayList<>();
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();


        for(int i=0; i < tasks.length; i++){
            Task temp = new Task(i, tasks[i][0], tasks[i][1]);
            task.add(temp);
        }

        Collections.sort(task, (o1, o2) -> {
            return o1.start!=o2.start ? o1.start-o2.start : o1.processing-o2.processing; // 시작 시간, 작업 시간 기준  오름차순 정렬
        });
        
        taskQueue.add(task.get(k++)); // 첫 번째 작업
        endTime += task.get(0).start;

        while(true) {
            currentTask = taskQueue.poll(); // 방금 다 한 작업
            endTime += currentTask.processing; // 끝났을 때의 시간
            result[r++] = currentTask.index; // 다 한 작업 결과에 추가

            if(r == task.size()) return result; // 작업을 다 추가 했다면 종료

            if(k < task.size()){
                while(endTime >= task.get(k).start){ // 끝났을 때의 시간보다 start 가 작은 애들 전부 queue에 넣어줌
                    taskQueue.add(task.get(k));
                    k++;
                    if(k > task.size()-1) break;
                }
            } 
            if(taskQueue.isEmpty() && k < task.size()){ // 작업이 남았는데 start시간이 늦어서 큐에 아무것도 못 들어갔을 때
                taskQueue.add(task.get(k));
                endTime = task.get(k).start;
                k++;
            }
        }

    }

    class Task implements Comparable<Task> {
        public int index;
        public int start;
        public int processing;

        public Task(int i, int s, int p) {
            index = i;
            start = s;
            processing = p;
        }
        @Override
        public int compareTo(Task task) {
            if (this.processing > task.processing) // 내림차 순
                return 1;
            else if (this.processing < task.processing)
                return -1;
            else {
                if(this.index > task.index) return 1;
                else return -1;
            }
        }
    }
}