[LeetCode] 1834. Single-Threaded CPU

- Problem

1834. Single-Threaded CPU

오랜만에 한 시간 붙잡았다.
열받네

---

- 첫 번째 풀이 (오답)

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        heap = sorted([(v[0], v[1], i) for i, v in enumerate(tasks)], key = lambda x: (x[0], x[1], x[2]))
        time = heap[0][0]
        stk = []
        answer = []

        while heap:
            while heap and heap[0][0] <= time:
                stk.append(heapq.heappop(heap))
            
            stk.sort(key = lambda x: (-x[1], -x[2]))
            _, p, i = stk.pop()
            time += p
            answer.append(i)

            while stk:
                heapq.heappush(heap, stk.pop())

        return answer

현재 작업 가능한 task를 모두 확인한 후, 작업 시간이 가장 짧고 인덱스가 가장 낮은 값을 정렬하여 확인한다.

우선 순위에서 밀려난 task는 다시 heap에 삽입한다. 비효율적이다.

- 결과

짐작했지만 열받네.

- 정답 풀이

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        priority_tasks = sorted([v[0], v[1], i] for i, v in enumerate(tasks))
        i, N = 0, len(tasks)
        heap = []
        time = priority_tasks[0][0]
        answer = []

        while len(answer) < N:
            while i < N and priority_tasks[i][0] <= time:
                _, processing_time, task_index = priority_tasks[i]
                heapq.heappush(heap, (processing_time, task_index))
                i += 1
            
            if heap:
                processing_time, task_index = heapq.heappop(heap)
                time += processing_time
                answer.append(task_index)
            
            else:
                time = priority_tasks[i][0]
        
        return answer

- 결과

너무 하드한데요. 열받네