leetcode-253 Meeting Rooms II

# Given an array of meeting time 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 <= 10^4
# 0 <= starti < endi <= 10^6

import heapq

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

        # Sort meetings by start time
        intervals.sort(key=lambda x: x[0])

        # Min-heap to track end times of ongoing meetings
        heap = []
        heapq.heappush(heap, intervals[0][1])  # Add first meeting's end time

        for i in range(1, len(intervals)):
            start, end = intervals[i]

            # If earliest ending meeting has finished, reuse that room
            if heap[0] <= start:
                heapq.heappop(heap)

            # Add current meeting's end time
            heapq.heappush(heap, end)

        # Heap size = number of rooms needed
        return len(heap)

    # Approach 2: Chronological Ordering (Two Pointers)
    def minMeetingRooms2(self, intervals: List[List[int]]) -> int:
        # Separate start and end times
        starts = sorted([i[0] for i in intervals])
        ends = sorted([i[1] for i in intervals])

        rooms = 0
        max_rooms = 0
        start_ptr = 0
        end_ptr = 0

        while start_ptr < len(starts):
            # If a meeting starts before earliest meeting ends
            if starts[start_ptr] < ends[end_ptr]:
                rooms += 1
                max_rooms = max(max_rooms, rooms)
                start_ptr += 1
            else:
                # A meeting has ended, free up a room
                rooms -= 1
                end_ptr += 1

        return max_rooms

# Heap: Time O(n log n), Space O(n)
# Two Pointers: Time O(n log n), Space O(n)
#
# Greedy Strategy:
# - Always reuse earliest available room (min-heap gives this)
# - Or: Track how many meetings are simultaneously active
#
# Key Insight: Don't need to track which specific room each meeting uses
# Just need to count maximum concurrent meetings