[LeetCode] 253. Meeting Rooms II

253. Meeting Rooms II

Medium

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

 

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

 

Constraints:

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

---

문제 풀이

• 미팅 시작 시간, 끝 시간의 배열이 주어진다. 
• 미팅 시간을 가지고 최소 몇개의 미팅룸이 필요한지 구해야한다. 
• 현재 미팅의 끝 시간과 다음 미팅의 시작시간이 같거나, 다음 미팅시작 시간이 크면 한개의 미팅룸을 중복해서 사용할 수 있다.

힙 O(NlogN)

• 미팅 시작 시간으로 배열을 정렬한다. 
• 새로만든 힙에 첫 미팅의 끝나는 시간을 넣는다. 
• 정렬된 인터벌 배열에서 힙에 들어간 맨 앞자리 숫자(미팅중에 가장 끝시간이 빨리 끝나는것)과 다음 미팅 시작시간과 비교한다.
• 만일 다음 미팅의 시작시간이 크거나 같으면 힙에서 값을 뺀다.
• 힙에 다음 미팅의 끝나는 시간을 넣는다. 
• [매번 힙에서 미팅의 끝나는 시간을 뺄때마다 가장 작은 값이 나오기 때문에 다음 미팅과 계속해서 비교가 가능하다.]
• [미팅 시간이 들어있는 인터벌도 시작시간으로 정렬되어 있기 때문이다.]

연대순 정렬(Chronological Ordering) O(NlogN)

• 이 풀이 방법은 미팅의 시작 시작과 종료 시간을 각각 정렬하는 것으로 시작한다. 
• 시작 시간과 종료 시간을 각각 비교하면서 미팅룸의 개수를 더하고 뺀다.
• 여기서, 만일 시작 시간이 종료 시간보다 크거나 같으면 종료 시간 포인터를 늘리고 미팅룸의 중복을 제거한다.
• [이 경우에 다음 미팅 시간이 현재 미팅 다음에 같은 미팅룸에서 진행될 수 있음을 의미한다.]
• 그리고 시작 시간 포인터를 하나 증가시키고 미팅룸의 개수를 증가시킨다.
• [즉, 매번 미팅룸의 개수를 늘리면서 시작 시간과 종료 시간을 비교하는데, 다음 미팅의 시작 시간이 이전 미팅 종료 시간보다 크거나 같으면 방을 같이 쓸 수 있기 때문에 개수를 줄이고 종료 시간 포인터를 늘려준 것으로 이해하면 된다.]

소스 코드

힙

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        free = []
        intervals.sort(key=lambda x:x[0])
        heapq.heappush(free, intervals[0][1])
        for p1, p2 in intervals[1:]:
            if free[0] <= p1:
                heapq.heappop(free)
            heapq.heappush(free, p2)
        return len(free)

연대순 정렬(Chronological Ordering)

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        free = 0
        s, e = 0, 0
        s_lst = sorted([i[0] for i in intervals])
        e_lst = sorted([i[1] for i in intervals])
        while s < len(intervals):
            if s_lst[s] >= e_lst[e]:
                e += 1
                free -= 1
            s += 1
            free += 1
            
        return free