Iteration

Overlapping Intervals

Interval Problems

Given an array of intervals intervals, return whether any of the intervals overlap. You should assume exclusive bounds on the intervals.

Example:

Overlapping Intervals - image
=> returns False\notag \large \texttt{=> returns False}

Example 2:

Overlapping Intervals - image
=> returns True\notag \large \texttt{=> returns True}
First Few Test Cases:
hasOverlap([[0, 2], [3, 4], [5, 6]])
# False
hasOverlap([[0, 3], [2, 4], [5, 6]])
# True
hasOverlap([[0, 1], [1, 2]])
# False

To do this in a single-pass, the idea is to sort the intervals by their starting location. This puts all the intervals in a convenient order, like this:

Overlapping Intervals - image

Now that the intervals are sorted, we can loop through them and check if the current interval overlaps with any other intervals. To do this, you have to check if the current interval overlaps with the previous interval.

The trick to doing this is to first find the condition when the intervals do not overlap, like this:

Overlapping Intervals - image

The intervals do not overlap if this condition holds:

prev[1] <= curr[0]

This means the intervals do overlap if the opposite holds:

prev[1] > curr[0]

Here's the code for checking this:

def hasOverlap(intervals):
    # sort the intervals by start time
    intervals.sort(key=lambda i: i[0])

    # loop over all intervals
    for i in range(1, len(intervals)):
        prev = intervals[i-1]
        curr = intervals[i]

        if prev[1] > curr[0]: # intervals overlap
            return True
            
    return False

Time Complexity O(nlog⁡n)O(n \log n). It takes nlog⁡nn \log n to sort the intervals, and then nn to iterate.

Space Complexity O(1)O(1)

Mark as Completed:
Submits:
hasOverlap
Test your code to get an output here!
hasOverlap(
)
Test your code to get an output here!