After coming back to this video like 10 times over the course of a month or 2 (giving up constantly on this problem), I finally came back today, listened to you explain the solution, after you explained it I didn't watch the coding this time and just tried it myself and it made sense. Finally progress...

Not the hero we deserve, but the hero we need

Your content is just wow ! The best there exists..Crisp...precise yet detailed ! And directly goes in the mind :)

There are many high votes solutions in Leetcode , but I just can't understand the concept behind their fancy solution. Fortunately, I found this great video and could nearly solve it by myself. Thanks a lot.

your explanation skills i found is bestest in the entire youtube

This is one of best explanations I found for the problem. Thank you NeetCode!

This is probably one of the most intuitive solutions I have seen for the Task Scheduler problem. Keep up the great work!

Thank you! I'd never be able to come up with this solution myself during the interview.

Sweet, this was my solution. Didn't see it in the official Leetcode solutions, but it made so much sense.

That's very intuitive solution we can use in the interview. Great.

This is so clearly explained. Thank you!

As always, great explanation. This was great to explain greedy algorithms. I'm somewhat concerned that still I'm not be able to figure out this approaches without some hints.

You are amazing...!!! Thanks for making this content available for free. Really helps a lot...!!!

Thanks to you, from your drawing solution I can get to the coding solution pretty easily

Man, this is so hard. I also saw a math or greedy solution in the solution section. Will I ever get a good job :'(

Thank you. As you said this is intuitive.

amazing and very simple approach

the only time you need to idle cpu is when there is no enough smaller tasks to fill the gaps! There for the result would be the maximum of either the total number of tasks or (maxTask * (1 + idleTime) - idleTime + howManyTimesTheMaxIs repeated ! (tested it on leetcode and got accepted)

Neetcode is the Mozart of LeetCode.

Hi NeetCode, thanks for the content. By the way, do you know when I need to heapify the heap and when I do not need to? I am thinking if I have to just push elements into the heap, then I don't need to heapify, but when I am popping from the heap, then I need to heapify the heap first?

This should be a hard.

Would it work with an ordered deck instead of a maxHeap?

I think the total time complexity of the final code should be O(n * len(tasks)) since we are iterating over all time slots available. So if we have a task array of [A, A, A, A] then the total number of loops will equal to n * len(tasks).

Optimized the code some. We can sort a single time and then simply use a deque() to avoid repeatedly pushing/popping from heap. It also really simplifies the internals of the while loop, since we don't need to track both a heap and a queue. def leastInterval(self, tasks: List[str], n: int) -> int: if n == 0: return len(tasks) # Sort the array in order of max frequency count = Counter(tasks) frequencies = list(count.values()) frequencies.sort(reverse=True) # For each frequency, associate it with the time at which it can be ran. Use +1 to offset 0-indexing jobs = deque([i+1, j] for i, j in enumerate(frequencies)) # Start the time variable at 0, so once we enter the loop we will be at time '1' # This allows us to directly return time at the end. time = 0 while jobs: time += 1 if time < jobs[0][0]: # The next task is not yet ready to run (still on cooldown) so wait one unit of time continue # The task is ready to run, so pop from the queue* and adjust its frequency cur_turn, cur_freq = jobs.popleft() cur_freq -= 1 if cur_freq > 0: jobs.append([cur_turn + n + 1, cur_freq]) return time

Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

thanks for this video!

Thank you!

Nice solution!

Very good 👏👏👏

I like how you say "this is pretty efficient solution" while showing 18% faster result xD

I don't think you can say O(log26) for the maxHeap, since it's not just one appearance per letter, it is task.length < 10^4, so there could be 10^4 pops * idle queue

Superb explanation

Great video

This has to be a Leetcode HARD

isn't time complexity eq to (N + N*log(N))? because at worst case you have to do up_heapify each time you pop() and insert.

How do people even think of this shit

Very cool pb i think

What is the intuition behind using the queue? Thanks love your videos

Hey, NeetCode or Viewers, I have a doubt, according to the code 16:30 After we push elements to the heap, don't we have to heapify it?

Hey...your explanation is excellent and very intuitive. But it is not the most optimized solution. Can you please help me by explaining the optimized approach to solving this problem?

How come if the first element in the queue == time, you push it back into the heap? This part feels non-intuitive, shouldn't you be processing this element and subtracting the count instead?

thanks bro

How come the complexity be O(n), n --> Number of characters, when you are iterating through the time required?

Some one please explain me , why the Time Complexity is O(n) in detail?

damn. This question is hard af hahaha

Do we really need a heap for this? since the number of letters are fixed, we can get away with using sorting the array at every time step as well.

Why the solution is not O(nlogn), as while loop is run n times and in each loop there is a heappop or heappush (logn), ignoring the idle time for simplicity sake?

Is the time complexity (tasks.size * n)?

Why do we increment the time first? Why not on the last line of the loop?

Why is this not O(nlogn)? The time complexity of heappop and heappush are both O(logn), and you perform them N number of times

Why is time complexity not O(nlogn)? Can anyone explain why log26 is constant

I watched this video 10 times, and could not understand what is the purpose of a queue and why it is Time + n. Took from me 1 (holi)day. Anyway, your video is still the best. How difficult to explain the process of this question

hmm there is a linear solution Just by frequency make slots and fit all remaining lower frequency slots there.

i did this and im getting time limit exceeded why??

Java Solution: class Solution { class Pair{ int rem_time; int next; Pair(int rem_time,int next){ this.rem_time=rem_time; this.next=next; } } public int leastInterval(char[] tasks, int n) { int cnt[]=new int[26]; for(char c:tasks) cnt[c-'A']++; PriorityQueueq=new PriorityQueue((a,b)->b-a); for(int i=0;i0){ q.add(cnt[i]); } } Queueq1=new LinkedList(); int time=0; while(q.size()>0||q1.size()>0){ time++; if(q.size()>0){ int cur=q.poll(); cur--; if(cur>0) q1.add(new Pair(cur,time+n)); } if(q1.size()>0 && q1.peek().next==time && q1.peek().rem_time>0){ Pair d=q1.poll(); q.add(d.rem_time); //if we use the below approach the time span of one of the values is never reached as the time is 1 and current time is already>1 // System.out.println(d.rem_time+" "+d.next); // if(d.rem_time>0) // q1.add(new Pair(d.rem_time,time+n)); } } return time; } }

Here is another way to do the same task_counts = {} for task in tasks: task_counts[task] = task_counts.get(task, 0) + 1 max_occurence = max(task_counts.values()) tasks_with_max_occurrences = sum(1 for count in task_counts.values() if count == max_occurence) min_time_needed = (max_occurence - 1) * (n + 1) + \ tasks_with_max_occurrences return max(min_time_needed, len(tasks))

what is the space complexity of this solution?

Is this question actually hard or is it just me? Because I tend to forget the solution multiple times.

What program do you use to draw out the solution?

Ive tried myself and also tried some codes from discuss section. none of them showed more than 20 to 25 % faster rate. edit: i m using C#

2 3 months before, I could not understand your videos and referred to Indian creators, but once I reached a certain level, I can now understand your solutions and code it up in C++.

There is no way anyone with reasonable IQ can conceive this method for the 1st time if they had not memorized this before.

Here is the C++ solution for the above logic class Solution { public: int leastInterval(vector& tasks, int n) { vector taskCounts(26, 0); for (char task : tasks) { taskCounts[task - 'A']++; } priority_queue pq; for (int count : taskCounts) { if (count > 0) { pq.push(count); } } queue q; int time=0; while(!pq.empty() || !q.empty()) { time++; if(!pq.empty()) { int val=pq.top(); pq.pop(); if(val-1!=0) { q.push({val-1,time+n}); } } if(!q.empty() && time==q.front().second) { pq.push(q.front().first); q.pop(); } } return time; } };

I'm quite interested in the optimal solution that you mention exists at the end. Is there a closed form solution? Also I think it's dishonest to disregard terms during the complexity analysis because the problem statement puts bounds on it, ie you say "it's O(n*log(26)) because the task type is an uppercase English letter". Well yeah, the problem also states that the task length is

damn! wow

How does Leetcode come up with these questions lol

This problem should be hard. Jesus.

How can I do the same by using positive counts in max heap?

Sir Is there is any way without using queue

Am I crazy or did you not explain how to handle an idle in the "Explaining Solution" section? You just explained an ideal case where no tasks require idling

why its going time limit exceeded? int leastInterval(vector& tasks, int n) { unordered_map mpp; for(auto task : tasks){ mpp[task]++; } priority_queue maxh; for(auto i : mpp){ maxh.push(i.second); } queue q; int time = 0; while(maxh.size() > 0 or q.size() > 0){ if(maxh.size() > 0){ int count = maxh.top(); maxh.pop(); time += 1; --count; if(count != 0) { q.push({count,time+n}); } } if(q.size() > 0 and q.front().second == time){ auto temp = q.front(); maxh.push(temp.first); q.pop(); } } return time; }

heapq is not defined, where is located heapq ?

Seriously dude, don’t you have a better solution than this ?

I can't be bothered

I want to leave a note why the true linear (and greedy) solution is possible and how it could be intuitive. In the video around 8:00 to 9:45, he's explaining the process of popping the max from the heap, adding to the queue and popping from queue then adding back to the heap. Notice that when the max value is popped from the heap, it is always gonna be added back being the greatest value in the heap. Why? Because in that one cooldown interval, every other value is gonna be reduced at most one before the max is removed from queue and added to the heap (once they are processed - reduced the count by one - they are going to the queue standing after the max (because the max is added first)). There's no jump in the order. So, once a max, always a max. After we've got this info, we can just get rid of both the heap and queue, and go with our greedy approach.

Should have just not used python, to keep it simple

Didn't like that explanation coupled to python implementation of a heap

such a bad question

Dude I know you are a python god but please just use normal syntax so everybody else dont have a headache trying to decode what a line means

I QUIT!

Here is a much more concise and easier to understand solution def leastInterval(self, tasks: List[str], n: int) -> int: n += 1 # n slots from when it finishes, n + 1 from when it started taskMap = {} # task -> last time it ran order = [] clock = 0 for t in tasks: taskMap[t] = c = taskMap.get(t, -n) + n # Will get 0, if not in the map print(f"Taks {t} can start no sooner than @:{c}") heapq.heappush(order, (c, t)) while order: c, t = heapq.heappop(order) clock = max(clock, c) print(f"Starting task:{t} @:{clock}") clock += 1 # 'Executing' the task return clock

Please solve this problem leetcode 855. Exam Room

Anyone get TLE for the java solution? class Solution { public int leastInterval(char[] tasks, int n) { Map map = new HashMap(); for ( char c : tasks) map.put((int)(c-'A'),map.getOrDefault((int)(c-'A'),0)+1); Queue q1 = new PriorityQueue( (a,b) -> b - a ); q1.addAll(map.values()); Queue q2 = new PriorityQueue( (a,b) -> a[0] - b[0] ); int rc =0; while ( !q1.isEmpty() || !q2.isEmpty() ) { rc++; if ( !q1.isEmpty() ) { int count = q1.poll() - 1; if ( count > 0 ) q2.add(new int[]{count,rc+n}); } if ( !q2.isEmpty() && q2.peek()[1] == rc ) { q1.add(q2.poll()[0]); } } return rc; } }

What is the complexity of heapify in python? is it O(n)