Problem statement

https://leetcode.com/problems/meeting-rooms-ii/

Solution

I like solution with line sweep approach, where we sort all starts and ends, and at each point of time we keep number of activated segments: $+1$ when we see start and $-1$ when we see end. Be careful, when we sort, and have ties, we first put ends, and then starts.

Complexity

Time complexity is $O(n\log n)$, space complexity is $O(n)$.

Code

class Solution:
    def minMeetingRooms(self, ints):
        points = sorted([(i, 1) for i,_ in ints] + [(j, -1) for _,j in ints])
        return max(accumulate(j for _,j in points))

Remarks

Another solution is the following: sort them by starts and then keep min heap with ends in each room. Then when we see new room, we compare the start $a_i$ with the root of our heap. If it is less than the root, it means, we need one more room, so we addone more element to the heap. If it is more than the root, we remove root, and add this end instead. Timecomplexity is $O(n\logn)$ both for sorting and for heap operations. Space complexity is $O(n)$