Skip to content

Commit ef9bac4

Browse files
author
Partho Biswas
committed
621. Task Scheduler
1 parent 4f812c3 commit ef9bac4

File tree

2 files changed

+33
-53
lines changed

2 files changed

+33
-53
lines changed

‎README.md

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -226,6 +226,7 @@ I have solved quite a number of problems from several topics. See the below tabl
226226
|01| [253_Meeting_Rooms_II](https://leetcode.com/problems/meeting-rooms-ii/)| [Python](leetcode.com/python/253_Meeting_Rooms_II.py)| [Official](https://leetcode.com/problems/meeting-rooms-ii/solution/) | Medium | --- |
227227
|02| [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/solution/)| [Python](leetcode.com/python/347_Top_K_Frequent_Elements.py)| [Helper 1](https://stackoverflow.com/questions/19979518/what-is-pythons-heapq-module), [Helper 2](https://stackoverflow.com/a/12373856/2089253), [heapq](https://docs.python.org/3.0/library/heapq.html), [Counter](https://docs.python.org/3/library/collections.html#collections.Counter) | Medium | --- |
228228
|03| [767. Reorganize String](https://leetcode.com/problems/reorganize-string/)| [Python](leetcode.com/python/767_Reorganize_String.py)| --- | Medium | Also check Greedy approach |
229+
|04| [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/)| [Python](leetcode.com/python/621_Task_Scheduler.py)| [Ex 1](https://leetcode.com/problems/task-scheduler/discuss/190390/Can-anyone-explain-to-me-what-the-problem-is-asking), [Ex 2](https://leetcode.com/problems/task-scheduler/discuss/130786/Python-solution-with-detailed-explanation), [Vid 1](https://www.youtube.com/watch?v=hVhOeaONg1Y), [Vid 2](https://www.youtube.com/watch?v=zPtI8q9gvX8), [Vid 3](https://www.youtube.com/watch?v=TV9VlHUR-Is), [Vid 4](https://www.youtube.com/watch?v=cr6Ip0J9izc&t=22s) | Medium | 📌 Extremely tricky. |
229230

230231

231232
### [Tries](https://leetcode.com/explore/learn/card/trie/)
@@ -281,7 +282,7 @@ I have solved quite a number of problems from several topics. See the below tabl
281282
|02| [1057. Campus Bikes](https://leetcode.com/problems/campus-bikes/)| [Python](leetcode.com/python/1057_Campus_Bikes.py)| [Video 01](https://www.youtube.com/watch?v=tG7GFge4-fQ), [Article 01](https://leetcode.com/problems/campus-bikes/discuss/371604/Python-Solution-Using-Dictionary-With-Explanation)| Medium | 📌 Solve [1066. Campus Bikes II](https://leetcode.com/problems/campus-bikes-ii/) using [DP](https://leetcode.com/problems/campus-bikes-ii/discuss/303471/Python-DP-vs-Backtracking-with-comments), [DFS](https://leetcode.com/problems/campus-bikes-ii/discuss/303383/Python-DFS-with-memorization) and [Priority Queue](https://leetcode.com/problems/campus-bikes-ii/discuss/303422/Python-Priority-Queue) |
282283
|03| [1007. Minimum Domino Rotations For Equal Row](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/)| [Python](leetcode.com/python/Minimum_Domino_Rotations_For_Equal_Row.py)| [Official](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/solution/), [Article 01](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/discuss/252242/JavaC%2B%2BPython-Different-Ideas)| Medium | 📌 Hard to spot if it is a Greedy |
283284
|04| [406. Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/)| [Python](leetcode.com/python/406_Queue_Reconstruction_by_Height.py)| [Article 1](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC%2B%2BJava-Solution), [Article 2](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89359/Explanation-of-the-neat-Sort%2BInsert-solution) | Medium | 📌 Fundamentals |
284-
|05| [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/)| [Python](leetcode.com/python/621_Task_Scheduler.py)| [Ex 1](https://leetcode.com/problems/task-scheduler/discuss/190390/Can-anyone-explain-to-me-what-the-problem-is-asking), [Ex 2](https://leetcode.com/problems/task-scheduler/discuss/130786/Python-solution-with-detailed-explanation), [Vid 1](https://www.youtube.com/watch?v=hVhOeaONg1Y) | Medium | 📌 Extremely tricky. Not done. Check later |
285+
|05| [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/)| [Python](leetcode.com/python/621_Task_Scheduler.py)| [Ex 1](https://leetcode.com/problems/task-scheduler/discuss/190390/Can-anyone-explain-to-me-what-the-problem-is-asking), [Ex 2](https://leetcode.com/problems/task-scheduler/discuss/130786/Python-solution-with-detailed-explanation), [Vid 1](https://www.youtube.com/watch?v=hVhOeaONg1Y), [Vid 2](https://www.youtube.com/watch?v=zPtI8q9gvX8), [Vid 3](https://www.youtube.com/watch?v=TV9VlHUR-Is), [Vid 4](https://www.youtube.com/watch?v=cr6Ip0J9izc&t=22s) | Medium | 📌 Extremely tricky. |
285286
|06| [392. Is Subsequence](https://leetcode.com/problems/is-subsequence/)| [Python](leetcode.com/python/392_Is_Subsequence.py)| [Ex 1](https://leetcode.com/problems/is-subsequence/discuss/87264/Easy-to-understand-binary-search-solution), [Ex 3](https://leetcode.com/problems/is-subsequence/discuss/87302/Binary-search-solution-for-follow-up-with-detailed-comments/144323) | Easy | 📌 |
286287
|07| **[55. Jump Game](https://leetcode.com/problems/jump-game/)** | [Python](leetcode.com/python/55_Jump_Game.py)| **[Official](https://leetcode.com/articles/jump-game/)** , [Art 1](https://tinyurl.com/yy9vyjyn)| Medium | 📌 **Must Check. Learned a lot** |
287288
|08| [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)| [Python](leetcode.com/python/45_Jump_Game_II.py)| [Vid 1](https://www.youtube.com/watch?v=cETfFsSTGJI), [Vid 2](https://www.youtube.com/watch?v=jH_5ypQggWg), [Vid 3](https://www.youtube.com/watch?v=vBdo7wtwlXs), [Art 1](https://tinyurl.com/yalsno6r) | Hard | 📌 |
@@ -539,8 +540,10 @@ Learn the following modules by heart. Just knowing all of the following items wi
539540
<b>Channels</b>
540541
01. [Tushar Roy - Coding Made Simple](https://www.youtube.com/channel/UCZLJf_R2sWyUtXSKiKlyvAw)
541542
02. [Back To Back SWE](https://www.youtube.com/channel/UCmJz2DV1a3yfgrR7GqRtUUA)
543+
03. [William Fiset](https://www.youtube.com/user/purpongie/featured)
544+
04. [Irfan Baqui](https://www.youtube.com/channel/UCYvQTh9aUgPZmVH0wNHFa1A)
542545

543-
<b>Graphs (Tree, BST, BIT, Segment Tree, etc)</b>
546+
<b>Tree (Tree, BST, BIT, Segment Tree, N-aray Tree, Trie etc)</b>
544547
01. [Fenwick Tree or Binary Indexed Tree - youtube](https://www.youtube.com/watch?v=CWDQJGaN1gY)
545548
02. [Binary Indexed Tree or Fenwick Tree - geeksforgeeks](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)
546549
03. [Binary Indexed Tree or Fenwick Tree - topcoder](https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/)
@@ -551,6 +554,12 @@ Learn the following modules by heart. Just knowing all of the following items wi
551554
08. [How does one decide when to use a Segment Tree or Fenwick Tree?](https://www.quora.com/How-does-one-decide-when-to-use-a-Segment-Tree-or-Fenwick-Tree)
552555
09. [What are the differences between segment trees, interval trees, binary indexed trees and range trees?](https://stackoverflow.com/questions/17466218/what-are-the-differences-between-segment-trees-interval-trees-binary-indexed-t)
553556

557+
<b>Graph(Dijkstra, Union Find, Kruskal, Prim's, Minimum Spanning Tree, Topological Ordering...etc)</b>
558+
01. [Graph Theory Playlist](https://tinyurl.com/rfgy88b)
559+
02. [Union Find \[Disjoint Set\] Playlist](https://tinyurl.com/srz7uua)
560+
03. [Disjoint Sets Data Structure - Weighted Union and Collapsing Find](https://www.youtube.com/watch?v=wU6udHRIkcc)
561+
0. []()
562+
554563
<b>Bit Manipulation</b>
555564
01. [Bit Manipulation - youtube](https://www.youtube.com/watch?v=7jkIUgLC29I)
556565
02. [Conversion of Binary, Octal and Hexadecimal Numbers](http://www.cs.ucr.edu/~ehwang/courses/cs120a/00winter/binary.pdf)

‎leetcode.com/python/621_Task_Scheduler.py

Lines changed: 22 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -5,69 +5,40 @@
55
# Task Scheduler - https://leetcode.com/problems/task-scheduler/
66

77
class Solution:
8-
def inverse(self, num):
9-
return -1 * num
108

9+
# Uses Heap. inspired from https://tinyurl.com/rmlstk3
1110
def leastInterval(self, tasks, n):
1211
"""
1312
:type tasks: List[str]
1413
:type n: int
1514
:rtype: int
1615
"""
17-
# What are the inputs here
18-
# - tasks - a list of strings the represent information we're processing
19-
# - n - the time between tasks of the exact same time. This would leave us room to process other tasks
20-
# we asking for here?
21-
# - We're looking for an int as an output. That's because we're returning a count
22-
# - We're looking for the minimum number of intervals that we're going to use for the problem
23-
24-
# How I think we're going to solve the problem
25-
# 1. We process the most important tasks often
26-
# - That's because we want to process everything quickly, and processing it quickly means processing the most frequent tasks immediately after the cooldown time is over is necessary.
27-
# 2. Determine my interval
28-
# - I want to be able to determine what step I'm at
29-
# 3. Create a dict of counts since I last processed my task
30-
31-
# Task map to store if we've seen the item before
32-
task_count = Counter(tasks)
33-
current_time = 0
34-
current_heap = []
35-
36-
# Sorting from least to greatest inside of the heap current_heap
37-
for k, v in task_count.items():
38-
heappush(current_heap,
39-
(self.inverse(v), k)) # Pushes item from least to greatest (hence the negative values)
40-
41-
# Here we're running through the entire heap and processing the sorted tasks
42-
while current_heap: # We're running until this list runs out because we intend to pop elements from it
43-
index, temp = 0, []
44-
while index <= n:
45-
current_time += 1 # We're counting the interval time here
46-
if current_heap:
47-
timing, taskid = heappop(current_heap)
48-
# We're checking to see if it's at the end of the overall count.
49-
# Remember that it was negative at the beginning
50-
if timing != -1:
51-
temp.append((timing + 1, taskid))
52-
# Checking to see if we're out of tasks. Exit the inner loop if both are true.
53-
# This will automatically exit out of the overall tasks
54-
if not current_heap and not temp:
55-
break
16+
taskFrequencies = Counter(tasks)
17+
totalIntervals = 0
18+
priorityQueue = []
19+
for k, v in taskFrequencies.items():
20+
heappush(priorityQueue, (-v, k))
21+
while priorityQueue:
22+
currentCoolingInterval, tempTaskHolder = -1, []
23+
while currentCoolingInterval < n:
24+
if priorityQueue:
25+
totalIntervals += 1
26+
currentCoolingInterval += 1
27+
taskFrequency, taskID = heappop(priorityQueue)
28+
if taskFrequency != -1:
29+
tempTaskHolder.append((taskFrequency + 1, taskID))
5630
else:
57-
index += 1
58-
# Because we transfered all of the items from the heap to temp, we're transferring them back to know if we should continue
59-
# heap -> If we're not out of tasks -> temp
60-
# temp -> Because we're not out -> heap
61-
for item in temp:
62-
heappush(current_heap, item)
63-
# We only stop if we're out of tasks
64-
# (Constantly checking the current_heap for if it's empty)
65-
return current_time
31+
if tempTaskHolder: # We still have task to process
32+
totalIntervals += (n - currentCoolingInterval)
33+
break
34+
for item in tempTaskHolder:
35+
heappush(priorityQueue, item)
36+
return totalIntervals
6637

6738

6839

6940
sol = Solution()
70-
tasks = ["A","A","A","B","B","B"]
41+
tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"]
7142
n = 2
7243
output = sol.leastInterval(tasks, n)
7344
print('Res: ', output)

0 commit comments

Comments
 (0)