Solutions

# Compute the max amount of meetings happening at the same time
# intervals


class Interval:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end

# Two arrays and two pointers - O(n log n) time, O(n) space
def minMeetingRooms(intervals: list[Interval]) -> int:
    startarr = [i.start for i in intervals]
    endarr = [i.end for i in intervals]
    startarr.sort()
    endarr.sort()

    active_meetings = 0
    s, e = 0, 0
    res = 0
    while s < len(intervals) and e < len(intervals):
        # Always take the earlier timestamp from either startarr or endarr
        if startarr[s] < endarr[e]:
            s += 1
            active_meetings += 1
        else:
            e += 1
            active_meetings -= 1
        res = max(active_meetings, res)
    return res


# Min heap keeping track of earliest finishing meeting - O(n log n) time, O(n) space
def minMeetingRooms(intervals: list[Interval]) -> int:
    import heapq
    intervals.sort(key=lambda x: x.start)
    min_heap = []

    res = 0
    for interval in intervals:
        # If the earliest-ending meeting finishes before the start of current meeting
        if min_heap and min_heap[0] <= interval.start: 
            # then remove current meeting
            heapq.heappop(min_heap)
        heapq.heappush(min_heap, interval.end)
        res = max(res, len(min_heap))
    
    return res


# Greedy / Sweep line algorithm - O(n log n) time, O(n) space
def minMeetingRooms(intervals: list[Interval]) -> int:
    time = []
    for i in intervals:
        time.append((i.start, 1))
        time.append((i.end, -1))

    time.sort(key=lambda x: (x[0], x[1]))

    res = count = 0
    for t in time:
        count += t[1]
        res = max(res, count)
    return res