Open seungriyou opened 3 months ago
https://leetcode.com/problems/task-scheduler/
most frequent element를 이용하는 greedy 문제이다.
ref: sol1, sol2 [!tip] most frequent task부터 순서대로 최소 간격(n)을 사이에 두고 배치해나가는 것이 포인트!
ref: sol1, sol2
[!tip] most frequent task부터 순서대로 최소 간격(n)을 사이에 두고 배치해나가는 것이 포인트!
n
cnts = {"A": 3, "B": 2}, n = 3이라면, most frequent task가 "A"이므로 이것부터 배치해본다.
cnts = {"A": 3, "B": 2}
n = 3
이때, / 는 most frequent task의 마지막 등장 직전의 위치를 표시한다. A _ _ _ A _ _ _ / A [______][______] (n + 1)칸 [_______] (max_cnt - 1)개 우선, most frequent task의 맨 마지막 등장을 제외하고(위에서 / 전까지), 확보해야 할 칸(= CPU cycle)의 수를 구해보면 (n + 1) * (max_cnt - 1)이 된다.
이때, / 는 most frequent task의 마지막 등장 직전의 위치를 표시한다.
/
A _ _ _ A _ _ _ / A [______][______] (n + 1)칸 [_______] (max_cnt - 1)개
우선, most frequent task의 맨 마지막 등장을 제외하고(위에서 / 전까지), 확보해야 할 칸(= CPU cycle)의 수를 구해보면 (n + 1) * (max_cnt - 1)이 된다.
(n + 1) * (max_cnt - 1)
이 값에 max_cnt와 같은 횟수로 등장하는 원소의 개수(= n_max_cnt)만큼 더해주면 필요한 interval의 최소 개수를 구할 수 있다.
max_cnt
n_max_cnt
하지만 cnts = {"A": 2, "B": 2, "C": 1, "D": 1}, n = 1이라면, most frequent task인 "A"를 먼저 배치했을 때
cnts = {"A": 2, "B": 2, "C": 1, "D": 1}
n = 1
A _ / A
위와 같이 되므로, 위의 식대로 구하면 (n + 1) * (max_cnt - 1) + n_max_cnt = 2 * 1 + 2 = 4이다.
(n + 1) * (max_cnt - 1) + n_max_cnt
2 * 1 + 2
4
그러나 이 값(4)은 전체 tasks의 개수(6)보다 작기 때문에 부족하다.
6
따라서 이때는 최소한 모든 tasks를 전부 돌기 위해 필요한 CPU cycle 값으로 len(tasks)를 반환해주어야 한다.
len(tasks)
max(len(tasks), (n + 1) * (max_cnt - 1) + n_max_cnt)
ref: sol
max heap q를 통해 most frequent 한 순서대로 각 task의 등장 횟수값을 pop한다.
q
이때의 포인트는, n + 1 만큼의 interval을 cycle로 잡아
n + 1
cycle
cycle 내 interval 수만큼 most frequent 한 순서대로 pop 하면서 tmp(등장 횟수 업데이트용) 및 tmp_time에 기록하고
tmp
tmp_time
이렇게 하면 한 cycle 내에서는 같은 task를 두 번 이상 pop 할 수 X
q에 원소가 남아있다면 이번 cycle을 꽉 채웠으며 다음 cycle에서 pop 할 task가 남아있다는 뜻이므로 cycle을 더해주고, 아니라면 이번 cycle을 꽉 채우지 못했을 수도 있으므로 이번 turn에서 기록한 tmp_time을 더해준다
res += cycle if q else tmp_time
는 것이다.
O(n)
O(nlog26)
log26
O(26)
O(1)
https://leetcode.com/problems/task-scheduler/editorial/
editorial 댓글에 있는 유사 문제도 풀어보기! (greedy + heap)
Approach
most frequent element를 이용하는 greedy 문제이다.
Idea 1: w/o Heap (1-Pass)
cnts = {"A": 3, "B": 2}
,n = 3
이라면, most frequent task가 "A"이므로 이것부터 배치해본다.이 값에
max_cnt
와 같은 횟수로 등장하는 원소의 개수(=n_max_cnt
)만큼 더해주면 필요한 interval의 최소 개수를 구할 수 있다.하지만
cnts = {"A": 2, "B": 2, "C": 1, "D": 1}
,n = 1
이라면, most frequent task인 "A"를 먼저 배치했을 때위와 같이 되므로, 위의 식대로 구하면
(n + 1) * (max_cnt - 1) + n_max_cnt
=2 * 1 + 2
=4
이다.그러나 이 값(
4
)은 전체 tasks의 개수(6
)보다 작기 때문에 부족하다.따라서 이때는 최소한 모든 tasks를 전부 돌기 위해 필요한 CPU cycle 값으로
len(tasks)
를 반환해주어야 한다.Idea 2: w/ Max Heap
max heap
q
를 통해 most frequent 한 순서대로 각 task의 등장 횟수값을 pop한다.이때의 포인트는,
n + 1
만큼의 interval을cycle
로 잡아cycle
내 interval 수만큼 most frequent 한 순서대로 pop 하면서tmp
(등장 횟수 업데이트용) 및tmp_time
에 기록하고q
에 원소가 남아있다면 이번cycle
을 꽉 채웠으며 다음cycle
에서 pop 할 task가 남아있다는 뜻이므로cycle
을 더해주고, 아니라면 이번cycle
을 꽉 채우지 못했을 수도 있으므로 이번 turn에서 기록한tmp_time
을 더해준다는 것이다.
Complexity
O(n)
/ (w/ heap)O(nlog26)
=O(n)
(n
= 원소 개수,log26
= max heap push/pop) (ref1, ref2)O(26)
=O(1)