LeetCode Meditations — Chapter 13: Intervals
In this new chapter, we are going to take a look at three interval problems: insert interval, merge intervals, and non-overlapping intervals.
An interval simply has a start and an end. The easiest way to think about them is as time frames.
With intervals, the usual concern is whether they overlap or not.
For example, if we have an interval [1, 3] and another [2, 5], they are clearly overlapping, so they can be merged together to create a new interval [1, 5]:
In order for two intervals not to overlap:
- the start of one should be strictly larger than the end of the other
newInterval[0] > interval[1]
or
- the end of the one should be strictly smaller than the start of the other
newInterval[1] < interval[0]
If both of these are false, they are overlapping.
If they are overlapping, the new (merged) interval will have the minimum value from both intervals as its start, and the maximum as its end:
[
min(newInterval[0], interval[0]),
max(newInterval[1], interval[1])
]
[
min(newInterval[0], interval[0]),
max(newInterval[1], interval[1])
]
Next up is the first problem in this chapter, Insert Interval. Until then, happy coding.