Calendar Matching

def calendarMatching(calendar1, dailyBounds1, calendar2, dailyBounds2, meetingDuration):
    i, j = 0, 0
    blockedIntervals = []
    bounds = findBounds(dailyBounds1, dailyBounds2)
                
    calendar1 = modifyIntervals(calendar1, bounds)
    calendar2 = modifyIntervals(calendar2, bounds)
    m,n = len(calendar1), len(calendar2)

    while i < m and j < n:
        interval1 = calendar1[i]
        interval2 = calendar2[j]
        if timeStringToTuple(interval1[0]) < timeStringToTuple(interval2[0]):
            curInterval = interval1
            i += 1
        else:
            curInterval = interval2
            j += 1
        updateLastIntervalOrCreateNew(blockedIntervals, curInterval)
    
    while i < m:
        curInterval = calendar1[i]
        updateLastIntervalOrCreateNew(blockedIntervals, curInterval)
        i += 1

    while j < n:
        curInterval = calendar2[j]
        updateLastIntervalOrCreateNew(blockedIntervals, curInterval)
        j += 1


    gaps = findTimeGapsWithMinMeetingTime(blockedIntervals, bounds, meetingDuration)
    return gaps

def findBounds(dailyBounds1, dailyBounds2):
    st1, end1 = timeStringToTuple(dailyBounds1[0]), timeStringToTuple(dailyBounds1[1])
    st2, end2 = timeStringToTuple(dailyBounds2[0]), timeStringToTuple(dailyBounds2[1])
    if st1 < st2:
        start = dailyBounds2[0]
    else:
        start = dailyBounds1[0]
    if end1 < end2:
        end = dailyBounds1[1]
    else:
        end = dailyBounds2[1]
    return [start, end]

def findTimeGapsWithMinMeetingTime(blockedIntervals, bounds, meetingDuration):
    gaps = []
    n = len(blockedIntervals)
    blockedIntervals.append([bounds[1], '00:00'])
    startShift, endShift = bounds
    prevEndTime = startShift
    for i, interval in enumerate(blockedIntervals):
        curStartTime = interval[0]
        timeGap = findTimeDifferenceInMinutes(prevEndTime, curStartTime)
        if timeGap >= meetingDuration:
            gaps.append([prevEndTime, curStartTime])
        prevEndTime = interval[1]
    return gaps

def doOverlap(interval1, interval2):
    st1, end1 = timeStringToTuple(interval1[0]), timeStringToTuple(interval1[1])
    st2, end2 = timeStringToTuple(interval2[0]), timeStringToTuple(interval2[1])
    return end1 >= st2

def mergeIntervals(interval1, interval2):
    st1, end1 = timeStringToTuple(interval1[0]), timeStringToTuple(interval1[1])
    st2, end2 = timeStringToTuple(interval2[0]), timeStringToTuple(interval2[1])
    if st1 < st2:
        start = interval1[0]
    else:
        start = interval2[0]
    if end1 < end2:
        end = interval2[1]
    else:
        end = interval1[1]
    return [start, end]
    
def timeStringToTuple(time):
    return list(map(int, time.split(':')))

def findTimeDifferenceInMinutes(time1, time2):
    firstHours, firstMins = timeStringToTuple(time1)
    secondHours, secondMins = timeStringToTuple(time2)
    return (secondHours-firstHours) * 60 + (secondMins-firstMins)
    
def updateLastIntervalOrCreateNew(blockedIntervals, curInterval):
    if blockedIntervals:
        lastBlockedInterval = blockedIntervals[-1]
        if doOverlap(lastBlockedInterval, curInterval):
            mergedInterval = mergeIntervals(lastBlockedInterval, curInterval)
            blockedIntervals[-1] = mergedInterval
        else:
            blockedIntervals.append(curInterval)
    else:
        blockedIntervals.append(curInterval)

def modifyIntervals(calendar, bounds):
    intervals = []
    startBoundString, endBoundString = bounds
    startBound, endBound = timeStringToTuple(bounds[0]),timeStringToTuple(bounds[1])
    for interval in calendar:
        intervalStart, intervalEnd = timeStringToTuple(interval[0]), timeStringToTuple(interval[1])
        if intervalStart < startBound and intervalEnd < startBound:
            continue
        elif intervalStart > endBound and intervalEnd > endBound:
            continue
        if intervalStart < startBound:
            interval[0] = startBoundString
        if intervalEnd > endBound:
            interval[1] = endBoundString
        intervals.append(interval)
    return intervals