Iteration

Interval Problems

Lesson

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 first interval starts before the second one, which is common in interval problems.

The condition for overlapping is the opposite:

You can do the same thing if you're given a 2D interval. You can furst find when 2D intervals do not overlap.

The condition for non-overlapping is this:

The condition for 2D intervals overlapping is the opposite:

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:

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

Mark as Completed:
Submits:
test
Test your code to get an output here!