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
Clarify if [1, 2] and [2, 3] are considered overlapping intervals
Clarify if [a, b] will strictly follow a < b
No intervals
Single interval
Two intervals
Non-overlapping intervals
Interval totally consuming within another
Duplicate intervals
Intervals which start right where another ends
Try to remember it as checking0 < 1 in both 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
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
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
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
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
def is_overlap(a, b):
return a[0] < b[1] and b[0] < a[1]def merge(a, b):
return [min(a[0], b[0]), max(a[1], b[1])]