gridland_metro.py

# source: https://www.hackerrank.com/challenges/gridland-metro
# video: https://youtu.be/H1Qbd652Oig

def gridlandMetro(n, m, k, tracks): # ALTERED NAME TO PLURAL 
    # tracks = [
    #    [row, col_start, col_end],
    #    ...
    # ]
    # sort by col start
    tracks.sort(key = lambda track: min(track[1], track[2])) # O(nlogn)

    # keep running total
    running_total = 0
    
    # create dictionary to hold rows
    last_col_end_by_rows = {}

    # loop through all tracks using dictionary to hold last col end
    for row, col_start, col_end in tracks: # O(n)
        # orient all tracks to go from left to right
        if col_end < col_start:
            col_start, col_end = col_end, col_start # swap positions

        # if row is new, add it to running history and add to total
        if not last_col_end_by_rows.get(row):
            last_col_end_by_rows[row] = col_end
            running_total += col_end - col_start + 1
        else:
            last_col_end_for_row = last_col_end_by_rows[row]
            # if current track interval does NOT overlap with previous
            if last_col_end_for_row < col_start: # don't set as equal, since last index/block already counted
                # add to total and update history
                last_col_end_by_rows[row] = col_end
                running_total += col_end - col_start + 1
            elif last_col_end_for_row < col_end: # there is some overlap and need partial lap and update history
                last_col_end_by_rows[row] = col_end
                running_total += col_end - last_col_end_for_row
            else: # current track is completely within previously counted territory
                continue
    return n * m - running_total # Total Time Complexity = O(nlogn)