253. Meeting Rooms II ☆★★★★

253. Meeting Rooms II

 

✅ 핵심 아이디어 (Min-Heap 방식)

회의실에서 가장 빨리 끝나는 회의부터 확인하면서,
새 회의가 그 전에 끝났다면 기존 방 재사용! 아니라면 새 방 필요!

---

✅ 전체 코드

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # 시작 시간 기준으로 정렬
        intervals.sort(key=lambda x: x[0]) # intervals.sort() 동일

        # 최소 힙: 각 방에서 회의가 끝나는 시각들을 저장
        min_heap = [] # minheap 사용해야 함

        for start, end in intervals:            
            """
            # 가장 빨리 끝나는 회의 시간과 비교 !!
            
            == 들어가는것 주의 !!
            leet code 에서는 end 시간과 start 시간이 같아도 안겹침!!
            """
            if min_heap and min_heap[0] <= start: minheap 에는 end 시간 넣었음
            	"""
                # 그냥 삭제, 지워지는 것은.. 회으실 안겹쳐서, 공유가능한거라서..
                """
                heapq.heappop(min_heap)  # 가장 빨리 끝난 회의 방 재사용

            heapq.heappush(min_heap, end)  # 새 회의의 종료시간 추가 (새 방 사용 or 재사용)
		
        """
        # 남은거 있으면, 따로 회의실 필요한거.
        """
        return len(min_heap)  # 현재 힙에 있는 방 수 = 동시에 필요한 회의실 수

---

🧠 예시: [[0,30],[5,10],[15,20]]

1. 정렬 후: [[0,30],[5,10],[15,20]]
2. Heap 상태 변화:
   • 0시 → [30]
   • 5시 → [10, 30] → 새 방 필요
   • 15시 → 10보다 크니까 10 제거 후 20 추가 → [20, 30]
3. 힙 크기 = 2 → 2개의 방 필요

---

📌 장점

• 직관적이고 빠름
• 시간복잡도: O(N log N)
  • 정렬: O(N log N)
  • heap 연산: O(log N)씩 → 총 N번

---

---

문제 설명에서는 

• 0 <= starti < endi <= 106

 

starti < endi 조건만 주어졌고,
"끝나는 순간과 시작이 같은 회의가 겹치지 않는다" 는 말은 명시적으로 쓰여 있지 않습니다.

---

✅ 하지만 왜 end <= start일 때 재사용 가능한가?

이건 LeetCode에서 암묵적으로 회의 시간이 반열림 구간 [start, end)로 정의하기 때문입니다.

---

📌 [start, end)란?

• 회의는 start에 시작해서 end 직전까지 열림.
• 즉, end 시점에는 이미 끝난 상태이므로,
  • end == start인 다른 회의는 겹치지 않음.
  • → 같은 방 재사용 가능.

---

🔍 LeetCode의 암묵적 규칙

• 이 문제(253번)를 포함해서 여러 시간간격 문제에서,
• 대부분 [start, end)로 해석해야 정답이 맞게 나옵니다.
• 실제로 [[10, 20], [20, 30]] 같은 입력이 주어졌을 때,
  • 1개의 방으로 가능한 걸로 처리됩니다.

---

✅ 정리

상황	겹침 여부	방 재사용
[10, 20]와 [20, 30]	❌ 안 겹침 (20 시점부터 새 회의)	✅ 가능
[10, 20]와 [19, 30]	✅ 겹침	❌ 불가

 

---

💬 결론

명시적으로 문제에 없지만,
LeetCode는 [start, end) 방식으로 판단하므로
end <= start일 때 방 재사용이 가능합니다.