Search code examples
algorithmdata-structurestime-complexityspace-complexity

Minimum number of meeting rooms

Apologies if this kind of question is not allowed here.

I came across this question: "Given a list of intervals representing the start and end time of ‘N’ meetings, find the minimum number of rooms required to hold all the meetings.". I solved it by finding the max number of intersecting intervals.

But in the answer section it is using min heap to keep track of meetings' end time and removing all the meetings that have ended and returns the max size that the min heap have reached at any point. What am I missing please?

Why using min heap is more efficient/the ideal answer?

Both solutions have O(nlogn) time complexity. Space complexity is the same for both answer mine is a little more efficient as I only need space for sorting.

I have attached both answers. Thanks in advance

enter image description here

enter image description here

Solution

  • Your solution looks fine in terms of complexity, but it seems like simply does not pass tests. One of the reason is your 'else' code block, it resets everything and starts count anew, but it looks like it should just decrease by one.

    So, it you have a test with

    start[0] = 0 end[0] = 1000 
start[1] = 0 end[1] = 1000 
start[2] = 1 end[2] = 2
start[3] = 3 end[3] = 10
start[4] = 5 end[4] = 6

    it is going to fail, because when index=2 and you visit else code-block, you will get count=1, but it is wrong, because it must be 2.