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.

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 not overlap.

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]]

Mark as Completed:

Submits:

test

Test your code to get an output here!