Skip to content

Instantly share code, notes, and snippets.

@tnvmadhav
Created July 9, 2023 06:24
Show Gist options
  • Save tnvmadhav/c308c414a3dfb53ba718b3df3e86282a to your computer and use it in GitHub Desktop.
Save tnvmadhav/c308c414a3dfb53ba718b3df3e86282a to your computer and use it in GitHub Desktop.
Peak Number of Meeting Rooms Needed
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)]
))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment