min_required_VMs.py

import heapq

# O(len(jobs) log len(jobs)) time
# O(len(jobs)) space
def min_required_VMs(jobs: list[list[int]]) -> int:
    """
    - job = [start,end) where e is exclusive
    - jobs are not sorted
    - 0<start<23
    - 1<end<24
    """
    if len(jobs) == 0: return 0
    if len(jobs) == 1 and len(jobs[0]) == 0: return 0

    # O(n) time
    # check for human-error in inputs
    for j in jobs:
        s,e = j
        if not (isinstance(s,int) and isinstance(e,int)):
            return -1

    max_concurrent_vms = 0
    # O(n) space
    running_vms = []

    # O(n log n)
    jobs.sort(key=lambda x: x[0])
    # O(n log n) time
    for j in jobs:
        if len(j) == 0: continue
        s,e = j
        # O(log n) amortized. 
        # We may pop n-1 elements, which takes (n-1) log (n-1) time. 
        # But averaged over n iteraions, it's O(log n).
        while len(running_vms) > 0 and s >= running_vms[0]:
            heapq.heappop(running_vms)
        heapq.heappush(running_vms, e)
        max_concurrent_vms = max(max_concurrent_vms, len(running_vms))
    return max_concurrent_vms

if __name__ == "__main__":
    """
    two interesting sets of input:
    - overlapping start/end times for consecutive jobs
    - no overlap

    we must remove jobs that have ended.
    This is tricky when there is overlap.
    """
    input1 = [
        [],                                 # empty
        [[]],                               # empty
        [['a', 'b']],                       # bad input
        [[1, 4], [4, 6], [6, 8], [8, 10]],  # no overlap
        [[1, 4], [2, 3], [3, 5], [5, 6]],   # overlap
        [[1, 4], [2, 3], [3, 6], [4, 5]],   # overlap
        [[1, 2], [2, 3], [3, 5], [3, 6]],   # overlap
        [[1, 4], [2, 3], [3, 5], [3, 6]]    # overlap
    ]

    output1 = [
        0,
        0,
        -1, # a way of telling caller something went wrong
        1,
        2,
        2,
        2,
        3
    ]
    for inp,out in zip(input1,output1):
        assert min_required_VMs(inp) == out