 Given an array of intervals `intervals`, return whether any of the intervals overlap. You should assume exclusive bounds on the intervals. Example: Example 2: 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: 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 over

Overlapping Intervals



-----problem-----

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


\b{Example:}



\image{e1,60}

$$\large \texttt{=> returns False}$$


\b{Example 2:}
\image{e2,60}

$$\large \texttt{=> returns True}$$



-----solution-----



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:

\image{0, 120}

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. \detail{
    You could theoretically check whether the current interval overlaps with both the previous \i{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 \b{not} overlap, like this:
\image{.5, 100}

The intervals do \b{not} overlap if this condition holds:


``
prev[1] <= curr[0]
``



This means the intervals \b{do} overlap if the opposite holds:
``
prev[1] > curr[0]

``


Here's the code for checking this:

\answer

\tc $O(n \log n)$. It takes $n \log n$ to sort the intervals, and then $n$ to iterate.

\sc $O(1)$




Iteration

Overlapping Intervals