Intervals
Interval problems are often provided as a List as input,
where each element is either a List or a Tuple of two elements.
«-----»
a b
«--------»
c d
«--------»
e f
The most common operations we can perform on a list of intervals are:
- Checking if they overlap.
- Merging overlapping intervals.
Overlapping intervals
Let's take a simple interval (a, b) as an example:
«-----»
a b
For another interval (c, d) to overlap, the c point must be somewhere between a and b:
«-----»
a b
«---...
c
Which forms the first condition . However, this not sufficient for the overlapping. In fact, let's have a look at this example:
«-----»
a b
«-»
c d
So, also the d must be in a certain position compared to the other interval,
which is behind a:
«-----»
a b
«--------»
c d
Then, our overlapping condition is: 1.
Merging intervals
Again, let's draw some intervals to get the idea:
«-------»
a b
«--------»
c d
«-------»
a b
«--------»
c d
It looks way simpler now:
x, y = [
max(a, c),
min(b, d),
]
You can use this simple trick to memorize the formula.
The symbol is always , so nothing special here.
For the actual condition, just memorize that you start from b and then go till a,
thus bc and da. Yes, this is not rocket science. 🚀