Meeting Rooms II - Leetcode 253 - Python

0:00 - Read the problem
2:05 - Drawing Explanation
8:43 - Coding Explanation

leetcode 253
Meeting rooms 2

#meeting #rooms #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[expansivegymnast]

This is one of those problems that looks really simple until you start actually coding it.

[rajdeepbiswas]

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!

[arjunbharadwaj]

Very clever solution. I think during an actual interview, I would have come up with a heap solution but not as clever as this.

[arnobpl]

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

[aravindravva]

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))

[dmytroivanovv]

Top explanation of this problem. Thank you, I got the whole point.

[tjsm]

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.

[jigardoshi]

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<int[]>((i1, i2) -> i1[1] - i2[1]);
for (var meeting: intervals) {
heap.offer(meeting);
if (heap.peek()[1] <= meeting[0])
heap.poll();
}
return heap.size();
}

[marhawk]

this is the one I’ve been waiting for. Many thanks NeetCode!

[aismitdas]

I never usually write comments on youtube, but I just had to for this video. But this is a very clear yet clever solution :) !

[theedmaster]

Oh my word, reframing this as the maximum times that meetings can overlap is so smart! I struggled for 20 minutes thinking about how to represent days by end times or something, haha

[RaoVenu]

Great explanation. I had an implementation with a Min heap but then I have to implement the minheap in javascript. This is way easier

[shonsanchez]

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.

[jinny]

I really like your videos. Your explanations are so clear that dummies like me also could understand 🤣

[almaskairatuly]

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).

[omeedtehrani]

This is an insanely clever solution. Thanks for sharing.

[DontTakeCrack]

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

[devdev]

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?

[Techgether]

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] <= start:
res[j] = end
found = 1
break

if not found:
res.append(end)
return len(res)

[rokasnavickas]

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