I was just asked this in an interview 10 minutes ago. This is similar to N-Fleet problems related to stack. I used a stack to calculate the room numbers.
This is a very clever solution, good work on finding it! But it's a bit hacky and very specific to this problem, so I feel we are missing out on learning crucial data structures i.e. priority queues Perhaps just mentioning it in the video would be pretty helpful!
@@dingus2332 Have minHeap storing the ends, then while the new interval's start is >= top of the heap, you pop from the heap and then push the new interval's end there. The max size of the heap at any moment is the answer.
@dingus2332 def min_meeting_rooms(self, intervals: List[Interval]) -> int: intervals.sort(key=lambda i : i.start) min_heap = [] rooms = 0 for i in intervals: heapq.heappush(min_heap, i.end) while min_heap[0]
@@dingus2332 heap solution: def min_meeting_rooms(self, intervals: List[Interval]) -> int: if not intervals: return 0 start,end = [],[] for inter in intervals: heapq.heappush(start,inter.start) heapq.heappush(end,inter.end) count,res = 0,0 while start and end: if start[0] < end[0]: heapq.heappop(start) count+=1 res=max(res,count) else: heapq.heappop(end) count-=1 return res
Great video! Here is the smaller solution with same time/space complexity as in the video: def minMeetingRooms(self, intervals: List[Interval]) -> int: timing = [] for intv in intervals: timing.append((intv.start, 1)) timing.append((intv.end, -1)) timing.sort() result = 0 ongoing = 0 for t in timing: ongoing += t[1] result = max(result, ongoing)
This can be done multiple ways , 1. create an array of max end time . 2. Then do +1 to the start and -1 for every interval > 3. Now find the max sum possible at any time . TC= O(N) space= O(max(EndTime))
Sometimes I narrow down my approach too much, I was trying to solve it using interval techniques but this solution use such a smart 2 pointer approach. Thanks.
Nice trick with 2 arrays for start and end times. One small note here, the code will be a little more efficient if we update the result only when we increase the count (because it's the only time the result can get bigger than whatever it was previously).
Nice explanation - I believe this can be easily solved using a minheap (especially in java where creating Start and End array would take many more lines) Here's my solution for java -- public int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]); var heap = new PriorityQueue((i1, i2) -> i1[1] - i2[1]); for (var meeting: intervals) { heap.offer(meeting); if (heap.peek()[1]
I also came up with the same approach, the time complexity is the same we compare the current interval start time with the min(end time) of prev meetings, if start time < min(end times), we cannot start the meeting using the existing rooms, we add a new room (push the current end time) else if start time >= min(end times), we can start the meeting in the room with min(end times) (pop from minheap and push the current end time) def min_meeting_rooms(self, intervals: List[Interval]) -> int: if not intervals: return 0 intervals.sort(key = lambda i: i.start) end_times = [intervals[0].end] heapq.heapify(end_times) for i in intervals[1:]: if i.start >= end_times[0]: heapq.heappop(end_times) heapq.heappush(end_times, i.end) return len(end_times)
@@Yuipser I believe the time complexity is a little slower? The worse case scenario would be n(log(n) + log(n)) or n(log(n^2)). Each heap push/pop operation takes log(n).
You can optimize your solution by only considering the max(res, count) when you are incrementing the count. Since count -1 will never be greater than the previous count.
Though this solution is super clever, I do not think that I could come up with that during an interview. Please use common algorithms and DS to solve these Leetcode questions.
This is my approach, my time complexity is also O(nlogn) and space complexity is O(n) where n is length of intervals elements. The nested loop has an amortized time complexity of O(n), correct me if i'm wrong! My logic is to keep track of any last end that has overlapped, then use each of these new last ends to check against the last start time. class Solution: def minMeetingRooms(self, intervals: List[Interval]) -> int: if not len(intervals): return 0 intervals.sort(key=lambda i:i.end) res = [intervals[0].end] for i in range(1,len(intervals)): start = intervals[i].start end = intervals[i].end found = 0 for j in range(len(res)): if res[j]
great solution. while i was looking at your visual diagram, i followed the same logic but simply inserted all start and end times into one array, sorted it, and differentiated whether or not that time was a start or end time. The sorting just has to make sure that if start == end, then end will go first due to the semi-inclusive nature of the problem. then it simply becomes if (t is a start time) num_meeting_rooms += 1; else num_meeting_rooms -= 1 TLDR: same logic and almost the same code but slightly different
The only problem with this is decreasing rooms, which gives a false perception of why we are decreasing rooms, as the rooms will remain same, but in this implementation i will not be increased when we are increasing j, but it will increase again when value at i < j, so in this example if i = 4 it denotes that max has correct number of room upto i =3, and i is still in process, if we increment i in each iteration , then we don't need to do --rooms in else part, which is more intuitive to the users, same as restaurant problem of cses and taking one dimensional array to solve it is more intuitive as it can give the clear picture of how many rooms/ customers are there at any one particular point of time
Thanks! I like your more intuitive approach, it's easier to understand and remember for the future. I expected a lot more comments about this than just one.
Great job as always. I did it slightly different, where I created essentially a stack of meetings. So the output would look something like the example output: intervals.sort(key=lambda x:x.start) out=[[intervals[0]]] for i in range(1,len(intervals)): for l in out: if l[-1].end
@@PippyPappyPatterson Assuming worst case, it would be O(n^2). I don't think you would do O(nLogn+n^2) as the bigger rate of change takes priority. However, on average it likey O(nLogn). Not the best with my time complexity analysis, so someone create me if I'm wrong.
@@cc-to2jn Sweet, thanks for your thoughts! Do you know of any Khan_Academy/Leetcode style problems for evaluating time and space complexity? I feel like the only way I'll get better is if I grind out problems w/ immediate, automated feedback like leetcode solutions.
@@PippyPappyPatterson I am not aware of any such sources. Space and time complexity evaluation you kind of just learn as you do the problems. I would suggest watching some videos on the basics first however. There are a lot of great videos, these 2 are my fav: th-cam.com/video/Mo4vesaut8g/w-d-xo.html th-cam.com/video/D6xkbGLQesk/w-d-xo.html
I was going to use priority queue of end times, and int[] of start times, but your approach using int[] for start and end[] is simpler Main differences are using a PQ, it sorts as new values are added. No pointers are needed here to manage and no need to create new int arrays
One side note, sorted([i.start for i in intervals]) won't work in leetcode as the intervals is specified as List[List[int]], you'd have to use i[0] for start and i[1] for finish
The alternative solution to this would be similar to LeetCode 435 (Non-overlapping Intervals). The additional part is for every interval overlap, would be put to a list, then use that list as a new interval list. def minMeetingRooms(self, intervals: List[Interval]) -> int: count = 0 intervals.sort(key=lambda i:i.start)
while intervals: curr = intervals[0] count += 1 new_intervals = [] for i in intervals[1:]: if i.start < curr.end: if curr.end > i.end: curr = i new_intervals.append(curr) else: new_intervals.append(i) else: curr = i intervals = new_intervals return count
I attempted to solve this problem by using an adjacency list and graph traversal to count intersecting intervals but I didn't realize this was a bad approach until I spent a good amount of time pursuing it. How would you recommend being able to notice these incorrect approaches early?
if the starting pointer is already outside the length of the array, then that means that only the end intervals can come next. Due to that, the overlaps are only going to start decreasing and the conflicts will decrease. But we're looking for the max, so we can just stop here and avoid the unnecessary work.
I did a much simple solution for this problem without needing to sort the intervals at all - def minMeetingRooms(self, intervals: List[Interval]) -> int: timePointTotalMeets = defaultdict(lambda: 0) highestMeetingStartTime = 0 for interval in intervals: [start, end] = interval.start, interval.end timePointTotalMeets[start]+=1 timePointTotalMeets[end]-=1 highestMeetingStartTime = max(highestMeetingStartTime, start) conflictingMeets = 0 currentMeets = 0 for t in range(highestMeetingStartTime+1): currentMeets+=timePointTotalMeets[t] conflictingMeets=max(conflictingMeets, currentMeets) return conflictingMeets
Suppose there are 5 meetings. 2 of them are overlapping and 3 of them are overlapping. Your approach would give the answer as 5 whereas the actual answer is 3. So, you need to decrement the count.
This is great but I don't see any point in lowering the count since the highest result will always be the count that has not been reduced by 1? Maybe it's more comprehensive this way but you can just increment the result whenever the first condition is true and be good.
@Neetcode - Would this below simple solution with O(1) space not work : intervals.sort(key = lambda x: x.start) if len(intervals) == 0: return 0 cr = 1 # number of conference rooms for i in range(1,len(intervals)): if intervals[i],start < intervals[i-1].end: cr+=1 return cr I checked above code for the 2 test cases given and it did work. Do you see any edge cases where it might return incorrect result ?
if you dont sort the ends you may keep hitting a lot of starts and ends that you are not accounting for. technically if you sort the starts and your largest end point comes first as in the video, you will have all your meeting open by the time you hit 30 which is wrong.
I don't have leedcode premium, so I can't test this answer, but I think this works in O(nlogn) time for sorting and constant memory. I'm essentially incrementing room counts by 1 any time the next meeting start time is less than the last earliest meeting end time. Whenever I come across schedule conflict, I "bump" the meeting that ends later and keep the end time of the one that ends earlier and use that to compare other subsequent meeting times. I'd be curious if this is wrong or if this could actually be a better solution. def min_meeting_rooms(self, intervals: List[Interval]) -> int: # Write your code here if len(intervals)
Case where 1st meeting whose end is less than 2nd overlap with 2nd. And 2nd overlap with 3rd here if you take min end then meeting 1s end will be considered and you wont get overlap when compared with 3rd
@@susheelgounder5333 I know you commented a month ago but would you be able to provide an input example? Since I came up with the same solution the original commenter wrote but I'm also not able to test since this is LC premium. Thanks!
how about we take in one array and take start as 1 and end as -1 like for this example array like - [ { 0,1}, { 5,1}, {10, -1}, {10, 1}, { 15, -1}, { 30, -1} ]
Not sure if this works: (dont have premium leetcode) def minMeetingRooms(intervals: list[Interval]) -> int: intervals.sort(key=lambda x: x.start) res = 0 for i in range(1, len(intervals)): prev = intervals[i-1] curr = intervals[i] if prev.end > curr.start: res += 1 if prev.end > curr.end: intervals[i].end = prev.end return res
Would someone point out what would be wrong with my solution? I implemented a stack solution. After I sort my intervals, I put the first end time in my stack and iterate through the intervals. If the current start I encounter is >= the stack top, I pop until the current start is greater than or equal to the top and push the current end in the stack. Otherwise I just push the end of the interval inside the stack.
As the ending time is not sorted when just pushing on to the stack, this approach would give a bigger value than the actual required meeting rooms. Try out this example (4,9), (9,10), (4,17)
It's because the edge case is already accounted for in the else statement, which is basically saying the same thing as "if start[s] >= end[e]". In the case that the start and end values are equal to each other, only e is incremented (not s), because a meeting has to end before the other starts.
HI , did you try this test case [[1,5],[8,9],[8,9]] . Accoring to your solution , I think it will return error. please try this test case and write comment for the result
@NeetCode or anyone can you please explains in bit detail how it's( NlogN) as time complexity, getting a little difficult to understand as I'm new in python. is it for sorting time complex will be (NlogN) and loop 0(N), hence its (NlongN)?
Sorting time is N Log N Going through the interval list is N That's N + N Log N, because you aren't going through the intervals at the SAME TIME AS the sorting (well you are during the sort, but you understand what I mean). So, you drop the N since you're looking for the biggest (almost worst) time, which is N LOG N. Anytime you do two operations together, they are multiplied, like a for loop inside another for loop. (M*N) If you have two for loops separate from each other, they are added (M+N)
The short answer is because anytime you sort an array, the theoretical best time complexity for a comparison based sorting algorithm is NLogN. Since the rest of the code runs in linear time, the time complexity is dominated by the sorting - so we drop the time it takes to run through the intervals. Therefore, we say NLogN
Python solution, easier to understand and remember class Solution(object): def minMeetingRooms(self, intervals): """ :type intervals: List[List[int]] :rtype: int """ sorted_intervals = [] rooms = 0 max_rooms = float("-inf") for i, each in enumerate(intervals, 1): sorted_intervals.append([each[0], 1, i]) sorted_intervals.append([each[1], -1, i]) sorted_intervals.sort() for start, time, event_id in sorted_intervals: if time != -1: rooms += 1 max_rooms = max(rooms, max_rooms) else: rooms -= 1 return max_rooms Python solution, easier to understand and remember
intervals = [(0,30),(5,10),(15,20)] intervals.sort(key = lambda i:i[0]) res = 1 prevEnd = intervals[0][1] for start, end in intervals[1:]: if start < prevEnd: res += 1 prevEnd = min(end, prevEnd) else: prevEnd = min(end, prevEnd) print(res) Is it a valid solution for this problem? Just followed the similar technique of the problem "Non overlapping intervals". Link: th-cam.com/video/nONCGxWoUfM/w-d-xo.html
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Meeting Rooms 1: th-cam.com/video/PaJxqZVPhbg/w-d-xo.html
This is one of those problems that looks really simple until you start actually coding it.
I was just asked this in an interview 10 minutes ago. This is similar to N-Fleet problems related to stack. I used a stack to calculate the room numbers.
@@vroomerlifts smart!
This is a very clever solution, good work on finding it!
But it's a bit hacky and very specific to this problem, so I feel we are missing out on learning crucial data structures i.e. priority queues
Perhaps just mentioning it in the video would be pretty helpful!
yes the beauty of this problem is to use the heap to keep track of the ending time.
Very clever solution. I think during an actual interview, I would have come up with a heap solution but not as clever as this.
Can you give solution from heap ?
@@dingus2332 Have minHeap storing the ends, then while the new interval's start is >= top of the heap, you pop from the heap and then push the new interval's end there. The max size of the heap at any moment is the answer.
@@dingus2332 My heap solution:
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort()
heap = [intervals[0][1]]
for i in range(1, len(intervals)):
if heap[0]
@dingus2332
def min_meeting_rooms(self, intervals: List[Interval]) -> int:
intervals.sort(key=lambda i : i.start)
min_heap = []
rooms = 0
for i in intervals:
heapq.heappush(min_heap, i.end)
while min_heap[0]
@@dingus2332 heap solution:
def min_meeting_rooms(self, intervals: List[Interval]) -> int:
if not intervals: return 0
start,end = [],[]
for inter in intervals:
heapq.heappush(start,inter.start)
heapq.heappush(end,inter.end)
count,res = 0,0
while start and end:
if start[0] < end[0]:
heapq.heappop(start)
count+=1
res=max(res,count)
else:
heapq.heappop(end)
count-=1
return res
Great video! Here is the smaller solution with same time/space complexity as in the video:
def minMeetingRooms(self, intervals: List[Interval]) -> int:
timing = []
for intv in intervals:
timing.append((intv.start, 1))
timing.append((intv.end, -1))
timing.sort()
result = 0
ongoing = 0
for t in timing:
ongoing += t[1]
result = max(result, ongoing)
return result
such an elegant solution. ty
Woooooo this is the one I’ve been waiting for. Many thanks NeetCode!
This can be done multiple ways ,
1. create an array of max end time .
2. Then do +1 to the start and -1 for every interval >
3. Now find the max sum possible at any time .
TC= O(N) space= O(max(EndTime))
TC is max end time I guess?
Sometimes I narrow down my approach too much, I was trying to solve it using interval techniques but this solution use such a smart 2 pointer approach. Thanks.
Top explanation of this problem. Thank you, I got the whole point.
Nice trick with 2 arrays for start and end times. One small note here, the code will be a little more efficient if we update the result only when we increase the count (because it's the only time the result can get bigger than whatever it was previously).
Nice explanation - I believe this can be easily solved using a minheap (especially in java where creating Start and End array would take many more lines)
Here's my solution for java --
public int minMeetingRooms(int[][] intervals)
{
Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]);
var heap = new PriorityQueue((i1, i2) -> i1[1] - i2[1]);
for (var meeting: intervals) {
heap.offer(meeting);
if (heap.peek()[1]
I also came up with the same approach, the time complexity is the same
we compare the current interval start time with the min(end time) of prev meetings, if start time < min(end times), we cannot start the meeting using the existing rooms, we add a new room (push the current end time)
else if start time >= min(end times), we can start the meeting in the room with min(end times) (pop from minheap and push the current end time)
def min_meeting_rooms(self, intervals: List[Interval]) -> int:
if not intervals:
return 0
intervals.sort(key = lambda i: i.start)
end_times = [intervals[0].end]
heapq.heapify(end_times)
for i in intervals[1:]:
if i.start >= end_times[0]:
heapq.heappop(end_times)
heapq.heappush(end_times, i.end)
return len(end_times)
@@Yuipser I believe the time complexity is a little slower? The worse case scenario would be n(log(n) + log(n)) or n(log(n^2)). Each heap push/pop operation takes log(n).
This is an insanely clever solution. Thanks for sharing.
I never usually write comments on youtube, but I just had to for this video. But this is a very clear yet clever solution :) !
You can optimize your solution by only considering the max(res, count) when you are incrementing the count. Since count -1 will never be greater than the previous count.
I was just thinking the same! Looked in the comments to see if I wasn't the only one
Though this solution is super clever, I do not think that I could come up with that during an interview. Please use common algorithms and DS to solve these Leetcode questions.
Great explanation. I had an implementation with a Min heap but then I have to implement the minheap in javascript. This is way easier
I really like your videos. Your explanations are so clear that dummies like me also could understand 🤣
This is my approach, my time complexity is also O(nlogn) and space complexity is O(n) where n is length of intervals elements. The nested loop has an amortized time complexity of O(n), correct me if i'm wrong! My logic is to keep track of any last end that has overlapped, then use each of these new last ends to check against the last start time.
class Solution:
def minMeetingRooms(self, intervals: List[Interval]) -> int:
if not len(intervals): return 0
intervals.sort(key=lambda i:i.end)
res = [intervals[0].end]
for i in range(1,len(intervals)):
start = intervals[i].start
end = intervals[i].end
found = 0
for j in range(len(res)):
if res[j]
great solution.
while i was looking at your visual diagram, i followed the same logic but simply inserted all start and end times into one array, sorted it, and differentiated whether or not that time was a start or end time. The sorting just has to make sure that if start == end, then end will go first due to the semi-inclusive nature of the problem.
then it simply becomes if (t is a start time) num_meeting_rooms += 1; else num_meeting_rooms -= 1
TLDR: same logic and almost the same code but slightly different
The only problem with this is decreasing rooms, which gives a false perception of why we are decreasing rooms, as the rooms will remain same, but in this implementation i will not be increased when we are increasing j, but it will increase again when value at i < j, so in this example if i = 4 it denotes that max has correct number of room upto i =3, and i is still in process, if we increment i in each iteration , then we don't need to do --rooms in else part, which is more intuitive to the users, same as restaurant problem of cses and taking one dimensional array to solve it is more intuitive as it can give the clear picture of how many rooms/ customers are there at any one particular point of time
Thanks! I like your more intuitive approach, it's easier to understand and remember for the future. I expected a lot more comments about this than just one.
Clear. Concise. Brilliant as always.
Great job as always. I did it slightly different, where I created essentially a stack of meetings. So the output would look something like the example output:
intervals.sort(key=lambda x:x.start)
out=[[intervals[0]]]
for i in range(1,len(intervals)):
for l in out:
if l[-1].end
oh wow interesting. Is this O(n⋅logn + n) or O(n⋅logn + n²) time?
@@PippyPappyPatterson Assuming worst case, it would be O(n^2). I don't think you would do O(nLogn+n^2) as the bigger rate of change takes priority. However, on average it likey O(nLogn).
Not the best with my time complexity analysis, so someone create me if I'm wrong.
@@cc-to2jn Sweet, thanks for your thoughts!
Do you know of any Khan_Academy/Leetcode style problems for evaluating time and space complexity?
I feel like the only way I'll get better is if I grind out problems w/ immediate, automated feedback like leetcode solutions.
@@PippyPappyPatterson I am not aware of any such sources. Space and time complexity evaluation you kind of just learn as you do the problems. I would suggest watching some videos on the basics first however. There are a lot of great videos, these 2 are my fav:
th-cam.com/video/Mo4vesaut8g/w-d-xo.html
th-cam.com/video/D6xkbGLQesk/w-d-xo.html
@@cc-to2jn thanks friend. Happy salary hunting!
I was going to use priority queue of end times, and int[] of start times, but your approach using int[] for start and end[] is simpler
Main differences are using a PQ, it sorts as new values are added. No pointers are needed here to manage and no need to create new int arrays
One side note, sorted([i.start for i in intervals]) won't work in leetcode as the intervals is specified as List[List[int]], you'd have to use i[0] for start and i[1] for finish
thank you
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I would also recommend checking out the line sweep algorithm to solve this
this is more readable while(i < length) {
if(start[i] < end[j]) {
++ days;
++i;
} else {
++j;
++i;
}
}
Thank you so much! The drawing was SUPER helpful to understand.
The alternative solution to this would be similar to LeetCode 435 (Non-overlapping Intervals).
The additional part is for every interval overlap, would be put to a list, then use that list as a new interval list.
def minMeetingRooms(self, intervals: List[Interval]) -> int:
count = 0
intervals.sort(key=lambda i:i.start)
while intervals:
curr = intervals[0]
count += 1
new_intervals = []
for i in intervals[1:]:
if i.start < curr.end:
if curr.end > i.end:
curr = i
new_intervals.append(curr)
else:
new_intervals.append(i)
else:
curr = i
intervals = new_intervals
return count
some of your videos are simply brilliant!
I understand this problem with your 2 min explain. what a god
Clear explanation!
I did using fenwick tree, same complexity O(nlogn)
I attempted to solve this problem by using an adjacency list and graph traversal to count intersecting intervals but I didn't realize this was a bad approach until I spent a good amount of time pursuing it. How would you recommend being able to notice these incorrect approaches early?
i also need help with this
hey buddy, any progress on this?
This is the best solution. Thanks
Thanks for lintcode ;)
can anyone elaborate more on while( s < len(intervals)) condition ?
if the starting pointer is already outside the length of the array, then that means that only the end intervals can come next. Due to that, the overlaps are only going to start decreasing and the conflicts will decrease. But we're looking for the max, so we can just stop here and avoid the unnecessary work.
I did a much simple solution for this problem without needing to sort the intervals at all -
def minMeetingRooms(self, intervals: List[Interval]) -> int:
timePointTotalMeets = defaultdict(lambda: 0)
highestMeetingStartTime = 0
for interval in intervals:
[start, end] = interval.start, interval.end
timePointTotalMeets[start]+=1
timePointTotalMeets[end]-=1
highestMeetingStartTime = max(highestMeetingStartTime, start)
conflictingMeets = 0
currentMeets = 0
for t in range(highestMeetingStartTime+1):
currentMeets+=timePointTotalMeets[t]
conflictingMeets=max(conflictingMeets, currentMeets)
return conflictingMeets
Is this necessary "res = max(res,count)". I think this will also work
if start[s] < end[e]:
count+=1
else:
e+=1
return count
Suppose there are 5 meetings. 2 of them are overlapping and 3 of them are overlapping. Your approach would give the answer as 5 whereas the actual answer is 3. So, you need to decrement the count.
@@subhashreebanik8131 What if we always move the start pointer to the next?
if start[s] < end[e]:
count+=1
else:
e+=1
s += 1
return count
Is there a way to do this while keeping track of prevEnd, similar to the non-Overlapping intervals problem?
I was asked this question in salesforce internship interview recently. Wasn't able to solve it 😣
really great explanation, you did a great job!
Nice, clear now!
TREMENDOUS EXPLANATION!
Great job
You are awesome, Thank you so much!!!!!
Thanks
you can also insert all times of the intervals + a flag if its a start/end_time it into a min_heap and check have a counter around it?
the vdo is very helpful, thanks a lot.
Great video
This is great but I don't see any point in lowering the count since the highest result will always be the count that has not been reduced by 1? Maybe it's more comprehensive this way but you can just increment the result whenever the first condition is true and be good.
U a God
@Neetcode - Would this below simple solution with O(1) space not work :
intervals.sort(key = lambda x: x.start)
if len(intervals) == 0:
return 0
cr = 1 # number of conference rooms
for i in range(1,len(intervals)):
if intervals[i],start < intervals[i-1].end:
cr+=1
return cr
I checked above code for the 2 test cases given and it did work. Do you see any edge cases where it might return incorrect result ?
can someone explain why we had to track `res, count` both?
It is because the time most rooms were occupied in the "whole time". And the count is about how many rooms are occupied in the moment
Can someone explain the intuition behind sorting the end array?
if you dont sort the ends you may keep hitting a lot of starts and ends that you are not accounting for. technically if you sort the starts and your largest end point comes first as in the video, you will have all your meeting open by the time you hit 30 which is wrong.
I don't have leedcode premium, so I can't test this answer, but I think this works in O(nlogn) time for sorting and constant memory. I'm essentially incrementing room counts by 1 any time the next meeting start time is less than the last earliest meeting end time. Whenever I come across schedule conflict, I "bump" the meeting that ends later and keep the end time of the one that ends earlier and use that to compare other subsequent meeting times.
I'd be curious if this is wrong or if this could actually be a better solution.
def min_meeting_rooms(self, intervals: List[Interval]) -> int:
# Write your code here
if len(intervals)
Wont work
Case where 1st meeting whose end is less than 2nd overlap with 2nd. And 2nd overlap with 3rd here if you take min end then meeting 1s end will be considered and you wont get overlap when compared with 3rd
@@susheelgounder5333 I know you commented a month ago but would you be able to provide an input example? Since I came up with the same solution the original commenter wrote but I'm also not able to test since this is LC premium. Thanks!
Could anyone answer why this solution doesn't work?
very clear！
how about we take in one array and take start as 1 and end as -1 like for this example array like - [ { 0,1}, { 5,1}, {10, -1}, {10, 1}, { 15, -1}, { 30, -1} ]
Why use res = max(res, count)? I'm not getting it.
At some point your count might decrease.
Res stores the max value count has reached
why do we need to update res on every iteration in the while loop?
wouldn't your solution get stuck in the while loop if start[s] == end[e]? I feel like it is missing a
elif start[s] == end[e]:
e += 1
s+=1
This condition will be covered in the else part
minimum platforms required variation
Not sure if this works: (dont have premium leetcode)
def minMeetingRooms(intervals: list[Interval]) -> int:
intervals.sort(key=lambda x: x.start)
res = 0
for i in range(1, len(intervals)):
prev = intervals[i-1]
curr = intervals[i]
if prev.end > curr.start:
res += 1
if prev.end > curr.end:
intervals[i].end = prev.end
return res
Could you use the same algorithm as the first Meeting Rooms, and just increase the count every time there's a conflict?
How would you know to decrease the count?
I don't think so, just tried that greedy approach and it didn't work
Would someone point out what would be wrong with my solution? I implemented a stack solution. After I sort my intervals, I put the first end time in my stack and iterate through the intervals. If the current start I encounter is >= the stack top, I pop until the current start is greater than or equal to the top and push the current end in the stack. Otherwise I just push the end of the interval inside the stack.
As the ending time is not sorted when just pushing on to the stack, this approach would give a bigger value than the actual required meeting rooms. Try out this example (4,9), (9,10), (4,17)
Which software do you use for drawing please?
Paint3D
Everyone can code, but it's an art to figure out an elegant solution.
```python
class Solution:
def __init__(self):
self.res = 0
def minMeetingRooms(self, intervals: List[Interval]) -> int:
if not intervals: return 0
intervals.sort(key=lambda x: x.end)
ovs = self.overlaps(intervals)
self.res += 1
if len(ovs):
self.minMeetingRooms(ovs)
return self.res
def overlaps(self, ints: List[Interval]) -> List[Interval]:
prev = None
res = []
for item in ints:
if prev is None or prev.end
this problem is similar to merge intervals
Hey, I was wondering why you didnt include the edge case in your code as start[s]==end[e] then s and e +=1
It's because the edge case is already accounted for in the else statement, which is basically saying the same thing as "if start[s] >= end[e]". In the case that the start and end values are equal to each other, only e is incremented (not s), because a meeting has to end before the other starts.
Out of curiosity, can't we sort, and try to count the number of overlapping intervals?
Can be solved in O(N) using difference array
how? Without sorting?
@@SreenathV Look into prefix sum algorithm
HI , did you try this test case [[1,5],[8,9],[8,9]] . Accoring to your solution , I think it will return error. please try this test case and write comment for the result
any alternative to leetcde and lintcode ?
Anyone please help.
GE for Great Explanation
@NeetCode or anyone can you please explains in bit detail how it's( NlogN) as time complexity, getting a little difficult to understand as I'm new in python. is it for sorting time complex will be (NlogN) and loop 0(N), hence its (NlongN)?
Yeah exactly !
Yes the buildin sort is nlogn
Sorting time is N Log N
Going through the interval list is N
That's N + N Log N, because you aren't going through the intervals at the SAME TIME AS the sorting (well you are during the sort, but you understand what I mean).
So, you drop the N since you're looking for the biggest (almost worst) time, which is N LOG N.
Anytime you do two operations together, they are multiplied, like a for loop inside another for loop. (M*N)
If you have two for loops separate from each other, they are added (M+N)
The short answer is because anytime you sort an array, the theoretical best time complexity for a comparison based sorting algorithm is NLogN. Since the rest of the code runs in linear time, the time complexity is dominated by the sorting - so we drop the time it takes to run through the intervals. Therefore, we say NLogN
Can anyone tell me why does it throw error when i use i.start and i.end in python. It says "list object has no attribute start".
use start = sorted([i[0] for i in intervals]) and end = sorted([i[1] for i in intervals]). That should resolve the error.
intervals is an object on Lintcode whereas it's a list on Leetcode
Python solution, easier to understand and remember
class Solution(object):
def minMeetingRooms(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
sorted_intervals = []
rooms = 0
max_rooms = float("-inf")
for i, each in enumerate(intervals, 1):
sorted_intervals.append([each[0], 1, i])
sorted_intervals.append([each[1], -1, i])
sorted_intervals.sort()
for start, time, event_id in sorted_intervals:
if time != -1:
rooms += 1
max_rooms = max(rooms, max_rooms)
else:
rooms -= 1
return max_rooms
Python solution, easier to understand and remember
lol how would someone even build the intuition to think of something like this 🤣
This is Klee's Algorithm, right??
Why does this algorithm work?
intervals = [(0,30),(5,10),(15,20)]
intervals.sort(key = lambda i:i[0])
res = 1
prevEnd = intervals[0][1]
for start, end in intervals[1:]:
if start < prevEnd:
res += 1
prevEnd = min(end, prevEnd)
else:
prevEnd = min(end, prevEnd)
print(res)
Is it a valid solution for this problem? Just followed the similar technique of the problem "Non overlapping intervals". Link: th-cam.com/video/nONCGxWoUfM/w-d-xo.html
That's what I'm wondering as well. Just don't have LeetCode Premium to check. Did you try running this on LintCode?
Sweep line!