 An "interval" is a set of points given by a `start` and an `end`. When you include the start and end points in the interval, it's called "inclusive" bounds, and is denoted with brackets `[start, end]`. When you don't include them in the interval, it's called "exclusive" bounds, and is denoted with parentheses `(start, end)`. Finding Overlap To find if intervals overlap, you should first consider when they do not overlap, like this: The condition for non-overlapping is this. We'll assume the fir

Interval Problems


An "interval" is a set of points given by a `start` and an `end`.


\image{0, 80}




When you include the start and end points in the interval, it's called "inclusive" bounds, and is denoted with brackets `[start, end]`.
When you don't include them in the interval, it's called "exclusive" bounds, and is denoted with parentheses `(start, end)`.



## Finding Overlap

To find if intervals overlap, you should first consider when they do \b{not} overlap, like this:

\image{2, 100}


The condition for non-overlapping is this. We'll assume the first interval starts before the second one, which is common in interval problems.

```
first[1] < second[0]
```



The condition for overlapping is the opposite:

```
first[1] >= second[0]
```

You can do the same thing if you're given a 2D interval.
You can furst find when 2D intervals do \b{not} overlap.
\image{4, 160}


The condition for non-overlapping is this:

```
# condition for no overlap

e[0] < start[0]    # is to the left
or s[0] > start[0] # is to the right
or s[1] < end[1]   # is below
or e[1] > start[1] # is above
```

The condition for 2D intervals overlapping is the opposite:


```
# condition for overlap

not (e[0] < start[0]
or s[0] > start[0]
or s[1] < end[1]
or e[1] > start[1])

```





## Tricks



You should usually sort intervals by their starting location. This lets you create greedy algorithms when not otherwise possible. For example, you might be given these intervals:


``
intervals = [[2,3], [1,2], [3,4], [0,1]]
``


You should usually sort them by their starting location, like this:

``
intervals.sort(key=lambda i: i[0])

intervals # [[0,1], [1,2], [2,3], [3,4]]
``













Iteration

Interval Problems

Finding Overlap

Tricks