Given an array of intervals intervals, return whether any of the intervals overlap. You should assume exclusive bounds on the intervals.
Example:
Example 2:
hasOverlap([[0, 2], [3, 4], [5, 6]])
# FalsehasOverlap([[0, 3], [2, 4], [5, 6]])
# TruehasOverlap([[0, 1], [1, 2]])
# FalseTo 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:
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. You could theoretically check whether the current interval overlaps with both the previous and next intervals. But this does twice as many checks as it needs to. You can run this loop to convince yourself of this: # double counting example for i in range(1,10): print(i-1) # previous interval print(i+1) # next interval <-- REDUNDANT *
The trick to doing this is to first find the condition when the intervals do not overlap, like this:
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 FalseTime Complexity O(nlogn). It takes nlogn to sort the intervals, and then n to iterate.
Space Complexity O(1)