253. Meeting Rooms II (Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum)

링크 - https://leetcode.com/problems/meeting-rooms-ii/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

우리는 Heap을 통해 이 문제를 풀 수 있다.

1. 먼저 intervals를 start시간에 맞춰 sorting한다.

2. heap을 생성하고 sorted interval에 for문을 돌린다. 그리고 매번 heap에는 end time을 넣는다.

3. interval을 heap에 넣기전에 interval의 start시간이 heap의 최상단의 값보다 큰지 확인한다. 크면 그 방의 미팅은 끝난것이므로 pop을 해준다.

4. 매번 heap의 max 길이값을 추적한다.

Code

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        ans = 0

        sorted_intervals = sorted(intervals, key=lambda x: x[0])
        heap = []

        for interval in sorted_intervals:
            while heap and heap[0] <= interval[0]:
                heapq.heappop(heap)
            heapq.heappush(heap, interval[1])
            ans = max(ans, len(heap))

        return ans

Complexity

Time Complexity: O(NlogN) Heap의 operation을 매번 수행하므로 N* logN이다.

Space Complexity: O(N) Heap의 크기는 최대 N개까지 늘어날 수 있다.