Spinach

# time: O(N) / space: O(N)
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        d = dict()
        if not nums:
            return 0
        for num in nums:
            if num in d:
                continue
            l,r = num-1, num+1
            left_value = d.get(l, 0)
            right_value = d.get(r, 0)
            d[num] = left_value + right_value + 1
            d[num-left_value] = d[num]
            d[num+right_value] = d[num]
        return max(d.values())

양 옆 끝의 값을 업데이트 하면서 진행

class Solution:
    def calculate(self, s: str) -> int:
        sta = []
        s = s.replace(" ", "")
        def calc(num, op):
            if op == '+':
                sta.append(num)
            elif op == '-':
                sta.append(-num)
            elif op == '*':
                sta.append(sta.pop() * num)
            else:
                sta.append(int(sta.pop() / num))

        num, operator = 0, '+'

        for idx, val in enumerate(s):
            if val in '+-*/':
                calc(num, operator)
                num = 0
                operator = val
            else:
                num = num * 10 + int(val)
        calc(num, operator)
        return sum(sta)

Leet Code 1834. Single-Threaded CPU

You are given n​​​​​​ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the i​​​​​​th​​​​ task will be available to process at enqueueTimei and will take processingTimei to finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

• If the CPU is idle and there are no available tasks to process, the CPU remains idle.
• If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. - If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
• Once a task is started, the CPU will process the entire task without stopping.
• The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

# 시간 초과
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        ret = []
        for idx, t in enumerate(tasks):
            t.append(idx)

        tasks = sorted(tasks, key= lambda t: t[1])
        time = 1

        while tasks:
            for t in tasks:
                if t[0] <= time:
                    time += t[1]
                    ret.append(t[2])
                    tasks.remove(t)
                    break
            else:
                time += 1

        return ret

-> Time Complexity O(N^2)
스케쥴링 시 현재 실행 가능하며, 가장 짧은 processing time 인 task 를 골라야 함

task 를 min heap q 에 넣은(nlog(n))한 뒤, 각 선택에서 가장 짧은 실행가능한 task 고르기(log(n))

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        ret, heap= [], []
        tasks = sorted([[t[0], t[1], i] for i, t in enumerate(tasks)])
        time = tasks[0][0]
        i = 0
        while len(ret) < len(tasks):
            while i < len(tasks) and tasks[i][0] <= time:
                heapq.heappush(heap, (tasks[i][1], tasks[i][2]))
                i += 1
            if heap:
                process_time, task_idx = heappop(heap)
                time += process_time
                ret.append(task_idx)
            elif i < len(tasks):
                time = tasks[i][0]

        return ret

-> Time Complexity O(Nlog(N)) / Space Complexity O(N)