find_overlapping_cycles.coffee

findOverlappingIntervals = (intervals) ->
    # throw all dates into an array. each date object also knows whether it is a start or end
    # date. after sorting, each start you hit signifies an interval. each end you hit signifies an
    # interval ends. if the interval counter is greater than zero, it means there is an overlap

    # construct list of start and end dates from all intervals
    dates = []
    for interval, index in intervals
        startElement =
            type: 'start'
            date: interval.start
            intervalIndex: index
        endElement =
            type: 'end'
            date: interval.end
            intervalIndex: index
        dates.push startElement, endElement

    # sort date list
    dates.sort (a, b) ->
        if moment(a.date).isAfter b.date
            return 1
        if moment(a.date).isSame(moment(b.date)) and a.type is 'end' and b.type is 'start'
            # tiebreaker: edges are inclusive so end objects come before start objects
            return 1
        return -1

    # iterate over dates to determine overlaps and mark the overlapping intervals
    intervalCounter = 0
    isOverlapped = false
    for date in dates
        if date.type is 'start'
            intervalCounter++
        else
            intervalCounter--
            if intervalCounter > 0 or isOverlapped
                intervals[date.intervalIndex].setOverlapError()
            if intervalCounter is 0
                isOverlapped = false
            if intervalCounter is 1
                # used to handle marking the overlapped interval with the latest end date
                isOverlapped = true
    return

O(nlogn)