253. Meeting rooms ii

solve.py

from heapq import heapify, heappush, heappop

# 253. Meeting rooms ii
def solve(ints):

    if not ints:
        return True
    
    ints.sort(key=lambda x: x[0])

    # use min heap to track end times
    h = []
    heappush(h, ints[0][1])

    for i in range(1, len(ints)):
        
        curr = ints[i]
        earliest = heappop(h)

        # no conflict, update earlist to new meeting endtime
        if curr[0] > earliest:
            earliest = curr[1]
        else:
            heappush(h, curr[1])

        # add back value whether updated or not
        heappush(h, earliest)
        
    return len(h)

# ints = [[0,30], [5,10], [15,20]]
# ints = [[0,10], [11,20], [21,30]]
ints = [[1,5], [3,7], [8,14], [10,12], [9,16], [18,20]]
print(solve(ints))