@@JaspreetSingh-bh5hc Hey Jaspreet if you want to check out my newest video it's a graph problem: th-cam.com/video/4LvYp_d6Ydg/w-d-xo.html (dfs)! Otherwise when a matrix is involved it usually has to do with graph or when you're asked is one thing reachable from a certain point, or you're asked to find a path or paths in a problem. I hope this helps!
For those who are looking for an intuition I will try to explain.. suppose you need to schedule n number of meetings for your company . Now you will first schedule the meeting which has the first start time and then go one by one as per the start time ( This explains the sorting part) . Now suppose while scheduling the second meeting you check when is the first meeting getting over - if the first meeting end time is less than the second meeting start time so we could use the same room . So what he has done is - find the meeting which is ending earliest and if the current meeting happens after the earliest meeting end we could use the same room so he just updated the end time for that room ..... but suppose there is a conflict between the earliest meeting and current meeting so we need to push this current meeting separately in the heap and we cant really use the same room..... Visualise the elements in the heap like the rooms and the end time represents when each room will get free .. Hope this helps
@@fufuto with this approach if we don't increment the end time after each comparison, when there is no conflict then we would not knw which meeting will end at the earliest for the next iteration. Suppose we have [[5,9],[10,15],[12,13]. In meeting room 1 -- first meeting will end at 9, so we can accommodate next meeting in the same room which starts after the first meeting ends, now the Meeting room 1 is occupied till 15. Now comes the third meeting at 12, so we cannot use meeting room 1 anymore, since it is occupied till 15, that is why we update the time every time there is no conflict. And like in this case there is a conflict, we simply push it in the heap, meaning we have two meeting rooms now. Hope this clears things up!
For anyone who might be watching this in the future, please note that the problem was updated slightly such that intervals is now just a 2D array rather than using the custom class Intervals. So for sorting, you'd just use a[0] - b[0] as the comparator
@Adeel Exactly! it's very easy to find the problem solution on the Internet and this way of making videos it's just kind of reading the internet solutions without giving us any idea behind how to think about the problem , how to find the brute force solution and how to optimize it!
exactlyyy... simply typing the answer is not a big deal.. Instead spend 80% of time explaining the algorithm on whiteboard and 20% time displaying your typing skills!
Anyone can write code dude. Explain how you came up with the concept, what processes you went through while arriving at the concept. This is not a Java coding tutorial session.
Why are we using priorityQueue here? We can simply solve this problem with sorting array & checking if interval[i][1] > interval[i+1][1] & than increment an integer variable Can someone explain why exactly we need PriorityQueue here?
Why returning size gives the answer is not explained. I think, if you solve it on whiteboard (considering all edge cases) and then type code it will be very helpful.
Can we get answer if we return number of overlapping events? def findMeetinHallsUsingHashSet(arr): st ={} count=0 for each in arr: start=each[0] end = each[1] for i in range(start,end+1): if i not in st: st[i]=0 else: count+=1 break
return count Please help me I dont have leetcode premium account to run this.
So, after implementing Kevin's solution myself, the insight I came to is that the size of the priority queue represents the minimum number of rooms we will need, and each interval determines the start and end times for those rooms. We start by adding the earliest-starting meeting (0th meeting) to the priority queue. If we have n meetings with no overlapping meeting times, the priority queue will merge the rest of intervals into a single big interval for the 1 room we will need. On the other hand, if we have n meetings with a single conflict, we will add the later-starting meeting (current) to the pq. Then since there are no more overlapping conflicts, then either the earliest interval or both the earliest and current intervals will continue expanding (increasing end time) until we finish iterating through the list. We will have 2 intervals in the pq, which means 2 rooms needed. Drawing a visualization should help visualize what is happening in the priority queue For meetings (0,10), (5-20), (7-11), (11-15), (15-30), (22-31), (25-40): This is what it would look like if you drew the meetings on a piece of paper, following the priority queue's logic of adding non-overlapping meetings to the earliest ending time. 0--------------------------------10 11--------------15 22------------------------------31 5--------------------------------------------------20 25-------------------------------------------------------------------------40 7----------11 15-----------------------------------------------30 And since we're merging the intervals, here is what the intervals in the pq will look like by the end. 0-----------------------------------------------------------------------------------------------------------------31 5--------------------------------------------------------------------------------------------------------------------------------------------------40 7--------------------------------------------------------------------------------30 Priority Queue: (7,30), (0,31), (5,40) Hope this helps!
Heya, a small feedback: I think if you can explain the concept rather than walking through the code, that can be more useful to folks. For example, if you explain why did you pick priority queue or how did you come to this certain approach, that would be more beneficial than watching you writing code, imo.
So, after implementing Kevin's solution myself, the insight I came to is that the size of the priority queue represents the minimum number of rooms we will need, and each interval determines the start and end times for those rooms. We start by adding the earliest-starting meeting (0th meeting) to the priority queue. If we have n meetings with no overlapping meeting times, the priority queue will merge the rest of intervals into a single big interval for the 1 room we will need. On the other hand, if we have n meetings with a single conflict, we will add the later-starting meeting (current) to the pq. Then since there are no more overlapping conflicts, then either the earliest interval or both the earliest and current intervals will continue expanding (increasing end time) until we finish iterating through the list. We will have 2 intervals in the pq, which means 2 rooms needed. Drawing a visualization should help visualize what is happening in the priority queue For meetings (0,10), (5-20), (7-11), (11-15), (15-30), (22-31), (25-40): This is what it would look like if you drew the meetings on a piece of paper, following the priority queue's logic of adding non-overlapping meetings to the earliest ending time. 0--------------------------------10 11--------------15 22------------------------------31 5--------------------------------------------------20 25-------------------------------------------------------------------------40 7----------11 15-----------------------------------------------30 And since we're merging the intervals, here is what the intervals in the pq will look like by the end. 0-----------------------------------------------------------------------------------------------------------------31 5--------------------------------------------------------------------------------------------------------------------------------------------------40 7--------------------------------------------------------------------------------30 Priority Queue: (7,30), (0,31), (5,40) Hope this helps!
[5,10],[8,15],[17,20],[12,30] Here if we extract the min value from the heap then answer would be 3 .But if we extract the max value and compare with the start time and if the start time is greater than the value which is extracted or extract the next maximum value and compare it and so on .At the end put all the extracted value back into the heap.In this approach the answer would be 2 which is the expected one.
it's probably easier to learn to solve these heap problems in java or python than it would be to implement a heap in JS. you could also explain to interviewer that JS doesn't have a native heap/pq class and at least provide the interface to a pretend library without actually implementing it. or say you would include one of the many open-source js libraries for the heap. remember - interviewing is just as much explaining HOW you solve problems than solving them. your interviewers are trying to determine what it would be like to work with you, not scoring you on a test
We can do something like this in O(n) Have an array with index 0 to endoftheday iterate list and mark a[starttime]+=1 a[endtime]-=1 now iterate a array from 0 to EOD sum+=a[i] max=max(max,sum)
Hello Kevin, any idea why the lambda thing is not working in my eclipse? Arrays.sort(intervals, (a - b) -> a.start - b.start); Also when I type and submit your code, leetcode doesn't accept, it says- Line 18: error: ')' expected Arrays.sort(intervals, (a - b) -> a.start - b.start);
this is what I came up with, the intuition is to put all meeting time slots into a grid, assume each row represents a meeting, if from 5 to 30 is meeting, then i fill index 4 to index 29 with 1, rest leaving as 0, then if we look at each column, the column containing max amount of 1 . ex. 3st 1 then 3 is the rooms required. Not sure if i am right though. using System; namespace ConsoleApp1 { public class MeetingRoom { public void Solution() { int[][] timeSlots = new int[][] { new int[] { 0, 30 }, new int[] { 5, 10 }, new int[] { 15, 20}, new int[] { 3, 6}, }; int columns = int.MinValue; for (int i = 0; i < timeSlots.Length; i++) { var timeslot = timeSlots[i]; columns = Math.Max(columns, timeslot[1]); } int rows = timeSlots.Length; // after this grid population we have following grid //111111111111111111111111111111 //000001111100000000000000000000 //000000000000000111110000000000 //000111000000000000000000000000 // index5 contains most 1 (3st) at the same timeslot. so it requires least 3 rooms int[,] grid = new int[rows, columns]; for (int i = 0; i < rows; i++) { var slot = timeSlots[i]; for (int j = 0; j < columns; j++) { if (slot[0]
Hey ...What advice do u give to a person like me who knows the logic to a program but is unable to code it.I can write algo pretty easily but somehow can't run on compiler
Honestly, just sit down and practice. Work on easier problems and work your way up. Start with the fundamentals and build a strong foundation. Read cracking the coding interview. That would help a lot with studying and overall guidance.
Btw I'm going to have a Facebook Intern Interview at the end of this month. If you have any advice or want to have a quick chat I'd be grateful :) Cheers!
daro d that’s awesome congrats!!! If you need help preparing check out my Patreon page: www.patreon.com/KevinNaughtonJr. I’d recommend the “study buddy” or “onsite” tier!
I am not sure why you choose such a complex way to solve this! You can just use DP! def minMeetingRooms(intervals): """ :type words: List[List] :rtype: bool O(NLog(N)) """ sorted_intervals = sorted(intervals, key=lambda x: x[0]) roomEndTime = [sorted_intervals[0][1]] for i in range(1, len(sorted_intervals)): start = sorted_intervals[i][0] end = sorted_intervals[i][1] first_meeting = min(roomEndTime) if start < first_meeting: roomEndTime.append(end) else: roomEndTime[roomEndTime.index(first_meeting)] = end return len(roomEndTime)
But if you reference real life then you should know that there is no chance if one group finishes in 14h that another group will be able to start in 14h exactly and few minutes added to that one meeting will bee added and multiplied with each meeting after and if you have 10 meetings today and add just 2 minutes to each your start and end times will not be even close to your schedule.
You get the point and either way meetings IRL do get booked back to back in the same room i.e. my meeting in room #1 is from 12pm-1pm and you book room #1 for 1pm-2pm
@@KevinNaughtonJr so true. showcase your personality and joke about how this class won't help you deal with engineers & pm's standing outside the meeting room door waiting awkwardly for yours to end. "we have this room from 1-2......" LOL
Good solution Kevin. Thanks. My version. Have made it slightly more readable. private static int findMinMeetingRooms(int[][] input) { Arrays.sort(input, (arr1, arr2) -> Integer.compare(arr1[0], arr2[0])); int previousEnd = input[0][1]; PriorityQueue endtimes = new PriorityQueue(); endtimes.add(previousEnd); for (int i = 1; i < input.length; i++) { int currentBegin = input[i][0]; int currentEnd = input[i][1]; if (currentBegin > endtimes.peek()) { //If meeting room freed up endtimes.remove(); endtimes.offer(currentEnd); } else { //If no meeting rooms available endtimes.offer(currentEnd); } } return endtimes.size(); }
look up heapq - tons of examples online and similarly solved leetcode problems. the basic idea is you have a basic array and use static heapq library functions to remove / add elements. however, the python implementation uses the first value passed in the element tuple/array to do the sorting, so for min-heap you have to convert values to negative
Hey Kevin! Can we create a heap without using array?(Asking this with reference to the question "stream of integers coming and we have to find the median". We use two heaps in that question and heaps are implemented using arrays internally, stream can be of any size then how can that be stored in array? Would be a great help :)
Hey Ishita! I think I might know the question you're talking about, but I'm not sure honestly sorry :( if there's anything else I can do to help or if you have any other questions lmk and I'd be happy to try and help :)
It would be a great gesture if could make a video on someone's interview experience with Google and/or Facebook, the questions asked during interview, etc.. Thank you!
That's an awesome idea! Questions that people are seeing during their interviews are discussed in the Discord server but making a video on someone's general experience interviewing would be great!
Hi @Kevin. First of all, great video! If you want to make your solution even more efficient, you can replace a minHeap by a variable holding the earliest available room (i.e. earliest end time). Every time you have a conflict with the earliest available room, you gonna need another room, so here you also keep a counter to increment whenever this happens. That approach you end up saving O(n) space (all meetings conflict) and O(nlogn) time (n insertions) in the worst case, since you dont need to maintain a heap anymore. Keep on posting those videos! I really like them.
How would you update this earliest "end time" variable in constant time if we schedule another meeting in the same room and end up increasing its end time?
Great idea! But, your pseudo code doesn't work on this case [[2,15],[36,45],[9,29],[16,23],[4,9]]. var minMeetingRooms = function(intervals) { intervals.sort((a,b) => a[1] - b[1]) let earliestEndInterval = intervals[0], rooms = 0 intervals.forEach(interval => { if(interval[0] >= earliestEndInterval[1]) { earliestEndInterval = interval } else { rooms++ } }) return rooms }; How would you decide which one should be the earliestEndInterval ?
Hey! Can you please tell how a fresher should apply for SDE role at Facebook and Google? Like applying through their careers page or pinging the recruiters on LinkedIn
i think we can just solve it the same way train platforms question is solved. Add when start, subtract when end time comes. Keep track of max no of rooms. // leetcode.com/problems/meeting-rooms-ii/ class Node{ int time; String type; Node(int t, String s){ this.time = t; this.type = s; } } public int minMeetingRooms(int[][] intervals) { PriorityQueue pq = new PriorityQueue((x, y)-> { if(x.time == y.time) { if(x.type.equals("end")) return -1; if(y.type.equals("end")) return 1; } return x.time - y.time; }); for(int[] i : intervals){ pq.add(new Node(i[0], "start")); pq.add(new Node(i[1], "end")); }
int count = 0, min = 0; while(pq.size()!=0){ Node curr = pq.remove(); if(curr.type.equals("start")) count++; else count--; min = Math.max(min, count); } return min; } Pls let me know what you guys think.
Hey Man, You are doing amazing work. Kudos!!! Could you help to cover below google problems. I am having difficulties in solving these problems Redundant Connection II Number of Music Playlists Rectangle Area II
Thank you so much! It's hard to keep track of all the requests that come in for questions...I actually made a Discord server and one of the channels is specifically for requesting questions to be solved, but I'll see what I can do. Thanks for your support!
If you guys need help with anything leave a comment and let me know!
I never understand when i should use graph to solve a given problem. Any tricks? Need help with graphs algos
@@JaspreetSingh-bh5hc Hey Jaspreet if you want to check out my newest video it's a graph problem: th-cam.com/video/4LvYp_d6Ydg/w-d-xo.html (dfs)! Otherwise when a matrix is involved it usually has to do with graph or when you're asked is one thing reachable from a certain point, or you're asked to find a path or paths in a problem. I hope this helps!
@@KevinNaughtonJr Can you try LeetCode-409. Longest Palindrome
How to get to your level proficiency in java..!
please read my comment, in case you haven't got the notification for my public comment:)
For those who are looking for an intuition I will try to explain.. suppose you need to schedule n number of meetings for your company . Now you will first schedule the meeting which has the first start time and then go one by one as per the start time ( This explains the sorting part)
. Now suppose while scheduling the second meeting you check when is the first meeting getting over - if the first meeting end time is less than the second meeting start time so we could use the same room . So what he has done is - find the meeting which is ending earliest and if the current meeting happens after the earliest meeting end we could use the same room so he just updated the end time for that room .....
but suppose there is a conflict between the earliest meeting and current meeting so we need to push this current meeting separately in the heap and we cant really use the same room..... Visualise the elements in the heap like the rooms and the end time represents when each room will get free .. Hope this helps
nicely explained
My question is that why are we changing the times? Can't we just increment an integer (number of conference rooms) whenever times conflict.
@@fufuto with this approach if we don't increment the end time after each comparison, when there is no conflict then we would not knw which meeting will end at the earliest for the next iteration. Suppose we have [[5,9],[10,15],[12,13]. In meeting room 1 -- first meeting will end at 9, so we can accommodate next meeting in the same room which starts after the first meeting ends, now the Meeting room 1 is occupied till 15. Now comes the third meeting at 12, so we cannot use meeting room 1 anymore, since it is occupied till 15, that is why we update the time every time there is no conflict. And like in this case there is a conflict, we simply push it in the heap, meaning we have two meeting rooms now. Hope this clears things up!
Thank you sir. Wouldn't have understood this from the video at all.
For anyone who might be watching this in the future, please note that the problem was updated slightly such that intervals is now just a 2D array rather than using the custom class Intervals. So for sorting, you'd just use a[0] - b[0] as the comparator
thanks
Please spend more time on the intuition and less on coding. That would really help a lot.
Worst Explanation
@Adeel Exactly! it's very easy to find the problem solution on the Internet and this way of making videos it's just kind of reading the internet solutions without giving us any idea behind how to think about the problem , how to find the brute force solution and how to optimize it!
exactlyyy... simply typing the answer is not a big deal.. Instead spend 80% of time explaining the algorithm on whiteboard and 20% time displaying your typing skills!
Looks like he just looked up the answer and made a video, this has ZERO explanation.
Anyone can write code dude. Explain how you came up with the concept, what processes you went through while arriving at the concept. This is not a Java coding tutorial session.
Why are we using priorityQueue here? We can simply solve this problem with sorting array & checking if interval[i][1] > interval[i+1][1] & than increment an integer variable
Can someone explain why exactly we need PriorityQueue here?
Why returning size gives the answer is not explained. I think, if you solve it on whiteboard (considering all edge cases) and then type code it will be very helpful.
Nice and clean solution! I knew a heap should be used, but didn't realize size should be returned.
Can we get answer if we return number of overlapping events?
def findMeetinHallsUsingHashSet(arr):
st ={}
count=0
for each in arr:
start=each[0]
end = each[1]
for i in range(start,end+1):
if i not in st:
st[i]=0
else:
count+=1
break
return count
Please help me I dont have leetcode premium account to run this.
@@go_cool_travels No. Ran your code didn't work out. You can think of a counter-example.
@@wardenofthenorth-w5d Thanks bro!! I will try to fix.
So, after implementing Kevin's solution myself, the insight I came to is that the size of the priority queue represents the minimum number of rooms we will need, and each interval determines the start and end times for those rooms.
We start by adding the earliest-starting meeting (0th meeting) to the priority queue.
If we have n meetings with no overlapping meeting times, the priority queue will merge the rest of intervals into a single big interval for the 1 room we will need.
On the other hand, if we have n meetings with a single conflict, we will add the later-starting meeting (current) to the pq. Then since there are no more overlapping conflicts, then either the earliest interval or both the earliest and current intervals will continue expanding (increasing end time) until we finish iterating through the list. We will have 2 intervals in the pq, which means 2 rooms needed.
Drawing a visualization should help visualize what is happening in the priority queue
For meetings (0,10), (5-20), (7-11), (11-15), (15-30), (22-31), (25-40):
This is what it would look like if you drew the meetings on a piece of paper, following the priority queue's logic of adding non-overlapping meetings to the earliest ending time.
0--------------------------------10 11--------------15 22------------------------------31
5--------------------------------------------------20 25-------------------------------------------------------------------------40
7----------11 15-----------------------------------------------30
And since we're merging the intervals, here is what the intervals in the pq will look like by the end.
0-----------------------------------------------------------------------------------------------------------------31
5--------------------------------------------------------------------------------------------------------------------------------------------------40
7--------------------------------------------------------------------------------30
Priority Queue: (7,30), (0,31), (5,40)
Hope this helps!
Awesome Kevin!
ty!
can you give a C code for this?
Heya, a small feedback: I think if you can explain the concept rather than walking through the code, that can be more useful to folks. For example, if you explain why did you pick priority queue or how did you come to this certain approach, that would be more beneficial than watching you writing code, imo.
So, after implementing Kevin's solution myself, the insight I came to is that the size of the priority queue represents the minimum number of rooms we will need, and each interval determines the start and end times for those rooms.
We start by adding the earliest-starting meeting (0th meeting) to the priority queue.
If we have n meetings with no overlapping meeting times, the priority queue will merge the rest of intervals into a single big interval for the 1 room we will need.
On the other hand, if we have n meetings with a single conflict, we will add the later-starting meeting (current) to the pq. Then since there are no more overlapping conflicts, then either the earliest interval or both the earliest and current intervals will continue expanding (increasing end time) until we finish iterating through the list. We will have 2 intervals in the pq, which means 2 rooms needed.
Drawing a visualization should help visualize what is happening in the priority queue
For meetings (0,10), (5-20), (7-11), (11-15), (15-30), (22-31), (25-40):
This is what it would look like if you drew the meetings on a piece of paper, following the priority queue's logic of adding non-overlapping meetings to the earliest ending time.
0--------------------------------10 11--------------15 22------------------------------31
5--------------------------------------------------20 25-------------------------------------------------------------------------40
7----------11 15-----------------------------------------------30
And since we're merging the intervals, here is what the intervals in the pq will look like by the end.
0-----------------------------------------------------------------------------------------------------------------31
5--------------------------------------------------------------------------------------------------------------------------------------------------40
7--------------------------------------------------------------------------------30
Priority Queue: (7,30), (0,31), (5,40)
Hope this helps!
Hi Kevin, can you please make video on Google code review interviews?
What if we sort according to end times and use a dequeue to store the intervals returning the size as answer at the end of the process
[5,10],[8,15],[17,20],[12,30]
Here if we extract the min value from the heap then answer would be 3 .But if we extract the max value and compare with the start time and if the start time is greater than the value which is extracted or extract the next maximum value and compare it and so on .At the end put all the extracted value back into the heap.In this approach the answer would be 2 which is the expected one.
the answer would be 2. Last 2 meetings are not sorted by their start time in the your input that's why you get 3 rooms
i understood what is a min heap but why a priority queue is used instead of min heap im not able to connect
A priority queue in java is a min heap
Can you share list of important problem for amazon sde2?
For python, we can follow this code, as I found it easy to understand as well:
n=int(input())
a=list(map(int,input().split()))
if len(a)
what if i'm coding in a language that doesn't have a heap built in like JS? would i be expected to create a heap class?
it's probably easier to learn to solve these heap problems in java or python than it would be to implement a heap in JS. you could also explain to interviewer that JS doesn't have a native heap/pq class and at least provide the interface to a pretend library without actually implementing it. or say you would include one of the many open-source js libraries for the heap. remember - interviewing is just as much explaining HOW you solve problems than solving them. your interviewers are trying to determine what it would be like to work with you, not scoring you on a test
We can do something like this in O(n)
Have an array with index 0 to endoftheday
iterate list and mark
a[starttime]+=1
a[endtime]-=1
now iterate a array from 0 to EOD
sum+=a[i]
max=max(max,sum)
That is not O(N) . That is actually O(MAX - MIN) , if max - min is very large it will be worse.
you should draw the heap so that people can see how the time is allocated visually instead of just talking
Hello Kevin, any idea why the lambda thing is not working in my eclipse? Arrays.sort(intervals, (a - b) -> a.start - b.start);
Also when I type and submit your code, leetcode doesn't accept, it says-
Line 18: error: ')' expected
Arrays.sort(intervals, (a - b) -> a.start - b.start);
There is a typo on line 17. Should be corrected as followings:
PriorityQueue minHeap = new PriorityQueue((a,b) -> a.end - b.end);
Why do we care about the earliest ending meeting? Can someone explain that?
Looking forward to contents on System Design.
this is what I came up with, the intuition is to put all meeting time slots into a grid, assume each row represents a meeting, if from 5 to 30 is meeting, then i fill index 4 to index 29 with 1, rest leaving as 0, then if we look at each column, the column containing max amount of 1 . ex. 3st 1 then 3 is the rooms required. Not sure if i am right though.
using System;
namespace ConsoleApp1
{
public class MeetingRoom
{
public void Solution()
{
int[][] timeSlots = new int[][] {
new int[] { 0, 30 },
new int[] { 5, 10 },
new int[] { 15, 20},
new int[] { 3, 6},
};
int columns = int.MinValue;
for (int i = 0; i < timeSlots.Length; i++)
{
var timeslot = timeSlots[i];
columns = Math.Max(columns, timeslot[1]);
}
int rows = timeSlots.Length;
// after this grid population we have following grid
//111111111111111111111111111111
//000001111100000000000000000000
//000000000000000111110000000000
//000111000000000000000000000000
// index5 contains most 1 (3st) at the same timeslot. so it requires least 3 rooms
int[,] grid = new int[rows, columns];
for (int i = 0; i < rows; i++)
{
var slot = timeSlots[i];
for (int j = 0; j < columns; j++)
{
if (slot[0]
Hey ...What advice do u give to a person like me who knows the logic to a program but is unable to code it.I can write algo pretty easily but somehow can't run on compiler
Become a product manager?
Honestly, just sit down and practice. Work on easier problems and work your way up. Start with the fundamentals and build a strong foundation. Read cracking the coding interview. That would help a lot with studying and overall guidance.
learn to code
Btw I'm going to have a Facebook Intern Interview at the end of this month. If you have any advice or want to have a quick chat I'd be grateful :) Cheers!
daro d that’s awesome congrats!!! If you need help preparing check out my Patreon page: www.patreon.com/KevinNaughtonJr. I’d recommend the “study buddy” or “onsite” tier!
I am not sure why you choose such a complex way to solve this! You can just use DP!
def minMeetingRooms(intervals):
"""
:type words: List[List]
:rtype: bool
O(NLog(N))
"""
sorted_intervals = sorted(intervals, key=lambda x: x[0])
roomEndTime = [sorted_intervals[0][1]]
for i in range(1, len(sorted_intervals)):
start = sorted_intervals[i][0]
end = sorted_intervals[i][1]
first_meeting = min(roomEndTime)
if start < first_meeting:
roomEndTime.append(end)
else:
roomEndTime[roomEndTime.index(first_meeting)] = end
return len(roomEndTime)
We can do a simpler greedy approach without the use of priority queue
But if you reference real life then you should know that there is no chance if one group finishes in 14h that another group will be able to start in 14h exactly and few minutes added to that one meeting will bee added and multiplied with each meeting after and if you have 10 meetings today and add just 2 minutes to each your start and end times will not be even close to your schedule.
You get the point and either way meetings IRL do get booked back to back in the same room i.e. my meeting in room #1 is from 12pm-1pm and you book room #1 for 1pm-2pm
@@KevinNaughtonJr so true. showcase your personality and joke about how this class won't help you deal with engineers & pm's standing outside the meeting room door waiting awkwardly for yours to end. "we have this room from 1-2......" LOL
Hi Kevin - I have a FB onsite. What coding and design questions should i prep for onsite?
Hey Nilesh .. How did your interview go ?
@@YameenYasin I have postponed it
@@niileshraaje9061 Can you share the interview questions ?
Good solution Kevin. Thanks. My version. Have made it slightly more readable.
private static int findMinMeetingRooms(int[][] input) {
Arrays.sort(input, (arr1, arr2) -> Integer.compare(arr1[0], arr2[0]));
int previousEnd = input[0][1];
PriorityQueue endtimes = new PriorityQueue();
endtimes.add(previousEnd);
for (int i = 1; i < input.length; i++) {
int currentBegin = input[i][0];
int currentEnd = input[i][1];
if (currentBegin > endtimes.peek()) {
//If meeting room freed up
endtimes.remove();
endtimes.offer(currentEnd);
} else {
//If no meeting rooms available
endtimes.offer(currentEnd);
}
}
return endtimes.size();
}
The above code gives wrong output for test case - [[1,5],[8,9],[8,9]] .o/p =1 expected = 2 Here is the same code that i used.. Am i missing anything ? Code is below -
public int minMeetingRooms(Interval[] intervals) {
if(intervals == null || intervals.length == 0){
return 0;
}
Arrays.sort(intervals , (a,b)-> a.start - b.start);
PriorityQueue minHeap = new PriorityQueue( (a,b) -> a.end - b.end);
minHeap.add(intervals[0]) ;
for(int i=1 ; i< intervals.length ; i++){
Interval current = intervals[i];
Interval earliest = minHeap.remove();
if(current.start >= earliest.end)
current.end = earliest.end;
else
minHeap.add(current);
minHeap.add(earliest);
}
return minHeap.size();
}
if(current.start >= earliest.end)
current.end = earliest.end; should be
earliest.end=current.end;
If we know the intuition we can also code , your purpose is to teach intution, not to write the code
anyone knows how to implement the minheap neatly in python ?
look up heapq - tons of examples online and similarly solved leetcode problems. the basic idea is you have a basic array and use static heapq library functions to remove / add elements. however, the python implementation uses the first value passed in the element tuple/array to do the sorting, so for min-heap you have to convert values to negative
Hey Kevin! Can we create a heap without using array?(Asking this with reference to the question "stream of integers coming and we have to find the median". We use two heaps in that question and heaps are implemented using arrays internally, stream can be of any size then how can that be stored in array?
Would be a great help :)
Hey Ishita! I think I might know the question you're talking about, but I'm not sure honestly sorry :( if there's anything else I can do to help or if you have any other questions lmk and I'd be happy to try and help :)
@@KevinNaughtonJr No problem Kevin :) Thank you very much for the vdios.
@@ishitarathi1186 Anytime!
Was asked this question for bloomberg
Sweet video, deffinetly a great question to know
Thanks Yoni!
It would be a great gesture if could make a video on someone's interview experience with Google and/or Facebook, the questions asked during interview, etc..
Thank you!
That's an awesome idea! Questions that people are seeing during their interviews are discussed in the Discord server but making a video on someone's general experience interviewing would be great!
Hi @Kevin. First of all, great video! If you want to make your solution even more efficient, you can replace a minHeap by a variable holding the earliest available room (i.e. earliest end time). Every time you have a conflict with the earliest available room, you gonna need another room, so here you also keep a counter to increment whenever this happens. That approach you end up saving O(n) space (all meetings conflict) and O(nlogn) time (n insertions) in the worst case, since you dont need to maintain a heap anymore. Keep on posting those videos! I really like them.
Awesome optimization Vitor thanks for sharing! Don't worry I'm going to keep posting these videos!
How would you update this earliest "end time" variable in constant time if we schedule another meeting in the same room and end up increasing its end time?
Great idea! But, your pseudo code doesn't work on this case [[2,15],[36,45],[9,29],[16,23],[4,9]].
var minMeetingRooms = function(intervals) {
intervals.sort((a,b) => a[1] - b[1])
let earliestEndInterval = intervals[0], rooms = 0
intervals.forEach(interval => {
if(interval[0] >= earliestEndInterval[1]) {
earliestEndInterval = interval
} else {
rooms++
}
})
return rooms
};
How would you decide which one should be the earliestEndInterval ?
There are ways to do it without a priority queue :/
I used a HashMap instead
Hey!
Can you please tell how a fresher should apply for SDE role at Facebook and Google? Like applying through their careers page or pinging the recruiters on LinkedIn
Hey Ishita I've got a video like this coming soon don't worry thanks for your support!
your approach explanation and code are awesome, thanks for this video
i think we can just solve it the same way train platforms question is solved. Add when start, subtract when end time comes. Keep track of max no of rooms.
// leetcode.com/problems/meeting-rooms-ii/
class Node{
int time; String type;
Node(int t, String s){
this.time = t; this.type = s;
}
}
public int minMeetingRooms(int[][] intervals) {
PriorityQueue pq = new PriorityQueue((x, y)-> {
if(x.time == y.time) {
if(x.type.equals("end")) return -1;
if(y.type.equals("end")) return 1;
}
return x.time - y.time;
});
for(int[] i : intervals){
pq.add(new Node(i[0], "start"));
pq.add(new Node(i[1], "end"));
}
int count = 0, min = 0;
while(pq.size()!=0){
Node curr = pq.remove();
if(curr.type.equals("start")) count++;
else count--;
min = Math.max(min, count);
}
return min;
}
Pls let me know what you guys think.
i lost at line 20 :P
Hey Man,
You are doing amazing work.
Kudos!!!
Could you help to cover below google problems.
I am having difficulties in solving these problems
Redundant Connection II
Number of Music Playlists
Rectangle Area II
Thank you so much! It's hard to keep track of all the requests that come in for questions...I actually made a Discord server and one of the channels is specifically for requesting questions to be solved, but I'll see what I can do. Thanks for your support!
#todo