coverIntervals.py

coverIntervals.py

# list_forecasts = [[1,3],[2,5]]

## cover(1pm, 7pm, [[1,3], [5,7]])
## return [[3,5]]

def cover(startTime, endTime, list_forecasts):
    n = len(list_forecasts)
    
    if n == 0:
        return [[startTime, endTime]]
    
    res = [list_forecasts[0]]
    
    for i in range(1,n):
        s = list_forecasts[i][0]
        e = list_forecasts[i][1]
        
        if s <= res[-1][1]:
            if e > res[-1][1]:
                res[-1][1] = e
        else:
            res.append(list_forecasts[i])
    
    # res = [[1,2],[4,5]]
    startInterval = None
    endInterval = None
    
    finalRes = []
    
    # find the start interval
    for i in range(len(res)):
        if res[i][0] <= startTime:
            startInterval = i
            break
    
    # find the end interval:
    for i in range(len(res)):
        if res[i][1] >= endTime:
            endInterval = i
            break
    
    print startInterval, endInterval
    
    if startInterval is None:
        finalRes.append([startTime, res[0][0]])
        startInterval = 0
    
    if endInterval is None:
        finalRes.append([res[-1][1], endTime])
        endInterval = len(res) - 1
    
    if startTime > res[startInterval][1]:
        finalRes.append([startTime, res[startInterval+1][0]])
        startInterval += 1
    
    if endTime < res[endInterval][0]:
        finalRes.append([res[endInterval-1][1], endTime])
        endInterval = endInterval - 1
    
    for i in range(startInterval, endInterval):
        finalRes.append([res[startInterval][1], res[startInterval+1][0]])
    
    return finalRes
   

startTime = 1
endTime = 7
list_forecasts = [[1,3],[3,7],[4,5]]

print cover(startTime, endTime, list_forecasts)