# Intervals

Interval problems aren't easy to spot and require some practice, try looking for ways to model the problem as a set of ranges/intervals

## Take noteβ¦

Clarify if

`[1, 2]`

and`[2, 3]`

are considered overlapping intervalsClarify if

`[a, b]`

will strictly follow`a < b`

## Corner cases

No intervals

Single interval

Two intervals

Non-overlapping intervals

Interval totally consuming within another

Duplicate intervals

Intervals which start right where another ends

## Techniques

### Overlap checking

Try to remember it as checking`0 < 1`

in both intervals

### Merge intervals

This is commonly used when looking to combine a bunch of intervals into a giant interval as long as there is some overlap between them

### Sorting first

Sort the array of intervals by the starting point or by ending point first

It is useful to think of why we need to sort and what information can be gathered from sorting first (i.e. what guarantees do we have once we sort)

Used to find the maximum number of non-overlaps, see Non-Overlapping Intervals

Sort by end and if the next interval starts after the current ending, we want to extend the ending only if there isnβt any overlaps

To maximize the most non-overlaps, we want to schedule the intervals that end earliest first

### Umbrella intervals

Instead of trying to think of discrete intervals, think of the entire interval as one whole, then operate on it as a whole

This can be useful when we don't actually care about the interval spans but rather whether or not the interval can reach a certain point like in Jump Game 2

### Line sweep

A relatively interesting class of problems where each interval represents a duration of an event occurring. When the interval starts, the event starts and when the interval ends, so does the event.

To model these problems, create events for the start/end of intervals and any additional intermediate events (usually arranged as

`(point, event_type)`

)The order of the events is dependent on how they are calculated, for instance, if the end of an interval should be counted before starting another interval

However, typically,

`end interval`

events should occur before`start interval`

ones

Sort this array and then simulate by running through it linearly

Common problems are the streetlights problem

### Operate at the interval level

Rather than focusing on individual values within an interval, try solving by breaking intervals into sub-intervals

Useful when optimizing problems that have too many values inside an interval

Take extra care when dealing with leading and trailing intervals that may be leftover from doing the partitioning

A good example of this is part 2 of Advent of Code 2023 Day 5

Last updated