[LeetCode Curated Algo 170] 253. Meeting Rooms II

문제 253. Meeting Rooms II

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

key word : 

비교해야 할것은 다음과 같다.

1) 회의 리스트가 정렬된 상태에서

2) 제일 먼저 시작한 회의의 종료시간이 새로운 회의의 시작시간과 비교하여,

    2.1) 작으면, 새로운 회의실이 필요하고
    2.2) 크면, 새로운 회의의 종료시간을 저장하여,
          비교 요청(새로운 회의)이 들어올 경우 비교 인자로 사용한다. 
    2.3) 새로 비교요청이 들어 올 경우, 가장 빨리 끝나는 회의와 비교해야한다.
          가장 빨리 끝나는 회의가 무엇인지,

          회의의 종료시간을 작은순으로 자동 정렬하여 저장할 데이터 구조로 heapq를 사용할 수 있다. 

# heapq 알기

https://www.daleseo.com/python-heapq/

 

 

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        
        #1. invervals가 비었는지 검사한다. 
        if not intervals:
            return 0
        
        #2. intervals를 시작시간을 기준으로 정렬한다. 
        # 시작시간 기준으로 되어있으므로, 
        # 나중에 들어오는건 앞선 시작시간보다 뒤 임이 보장된다. 
        # 따라서 시작한 회의의 종료시간과 새로운 회의의 시작시간의 순서를 비교하면된다. 
        intervals.sort(key= lambda x : x[0])
        
        #3. heapq에 제일 먼저 시작하는 회의의 종료시간을 넣는다. 
        free_rooms = []
        heapq.heappush(free_rooms, intervals[0][1])
        
        for new_meeting in intervals[1:]:
            #새로운 미팅의 시작시간이 가장 빨리 끝나는 룸의 종료시간(free_rooms엔 종료시간이 들어감)보다 뒤라면
            #이제 그 룸은 체킹 안해도되서 빼낸다. 
            if new_meeting[0] >= free_rooms[0]:
                heapq.heappop(free_rooms)
            
            heapq.heappush(free_rooms,new_meeting[1])
            
        
        return len(free_rooms)