To solve the “Minimize Meeting Rooms” problem, we can use a greedy algorithm. The idea is to keep track of the ongoing meetings and allocate new meeting rooms whenever a new meeting starts while making sure that there are no overlapping meetings in the same room.

from typing import List, Tuple

def min_meeting_rooms(meetings: List[Tuple[int, int]]) -> int:
    # Check if there are no meetings
    if not meetings:
        return 0

    # Separate the start times and end times of meetings
    start_times = [start for start, end in meetings]
    end_times = [end for start, end in meetings]

    # Sort the start times and end times separately
    start_times.sort()
    end_times.sort()

    num_rooms = 0  # Count of meeting rooms needed
    end_ptr = 0     # Pointer for the end times

    for start_time in start_times:
        # Check if a meeting has ended
        if start_time >= end_times[end_ptr]:
            # If a meeting has ended, reuse the room by incrementing the end_ptr
            end_ptr += 1
        else:
            # If no room is available, allocate a new room
            num_rooms += 1

    return num_rooms

# Example usage:
result1 = min_meeting_rooms([(0, 30), (5, 10), (15, 20)])
print(result1)
assert result1 == 2

result2 = min_meeting_rooms([(1, 5), (8, 9), (2, 6)])
print(result2)
assert result2 == 2

result3 = min_meeting_rooms([(7, 10), (2, 4)])
print(result3)
assert result3 == 1

Time Complexity:

The time complexity is O(N log N), where N is the number of meetings. The sorting of start times and end times takes O(N log N), and the iteration through the sorted start times or end times takes O(N). The dominant factor is the sorting.

Space Complexity:

The space complexity is O(N) as we use separate lists for start times and end times, each of size N.