Peak Number of Meeting Rooms Needed

meeting_rooms_2.py

from typing import List
from collections import defaultdict

class Solution:
    def min_meeting_rooms_worse(self, intervals: List[List[int]]) -> int:
        """
            TC: O(N^2), SC: O(N)
        """
        room_dict = defaultdict(list)

        #  O(NlogN)
        intervals.sort()

        # for each new interval: O(N)
        for interval in intervals:
            interval_added = False
            # for each room in dict
            for _, v in room_dict.items():  # O(1) --> O(N)
                new_room = False
                # for each interval in said room
                for i in v:
                    # if conflict, continue to next room, if no conflict,
                    if interval[0] < i[1]:
                        new_room = True
                        break
                    # if no next, append to room
                    continue
                if not new_room:
                    v.append(interval)
                    interval_added = True
                    break

            if not interval_added:
                room_dict[len(room_dict.keys())+1].append(interval)
        return len(room_dict.keys())


    def min_meeting_rooms_better(self, intervals: List[List[int]]) -> int:
        """
            TC: O(NLogN), SC: O(N)
        """
        boundary_map = defaultdict(int)
        mx, sum = 0, 0

        # O(N)
        for interval in intervals:
            boundary_map[interval[0]] += 1
            boundary_map[interval[1]] -= 1

        # O(NLogN) + O(N)
        for _, v in sorted(boundary_map.items()):
            sum += v
            mx = max(mx, sum)
        
        return mx

if __name__ == "__main__":
    s = Solution()

    print(s.min_meeting_rooms_better(
       [(0,5),(2,7),(6, 8)]
    ))