Crushing Tech Interviews with the Merge Intervals Pattern
This pattern is useful when dealing with interval questions. A lot of the questions will require us to merge overlapping intervals in a given list.
First step to answering a question like this is to answer the following question: How many ways can two intervals be positioned in relation to each other?
The answer is 6:
This diagram is key to our understanding of intervals! Now let's use this understanding to solve the following problem:
Given a list of intervals, merge all the overlapping intervals.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]
Although the input is sorted in the example given, this may not always be the case. The first step is to sort the input list so that
a.start <= b.start . This is will make things a lot simpler as you will see in a second.
One thing to notice, is that we only care about the cases where the intervals overlap. If we look at the previous image, the cases where the intervals overlap are:
2, 3, 4, 5. Also, we only care about cases where
a.start <= b.start. So that eliminates
5. Now we're only left with
2, 3, 4 !
Ok, we've simplified the problem a bit. Now lets look at how we would merge the cases
2, 3, 4 :
Can you notice the pattern with the start and end values of each merged interval?
Yep thats right:
- The start of the interval is always
- The end of the interval is the maximum between
Lets look at some code to cement this idea:
class Interval: def __init__(self, start, end): self.start = start self.end = end def merge_intervals(intervals: List[List[int, int]]) -> List[List[int, int]]: intervals.sort(key=lambda x: x) intervals = [Interval(interval, interval) for interval in intervals] # This is not needed but makes the code more legible. merged_intervals =  start = intervals.start end = intervals.end for interval in intervals[1:]: if interval.start <= end: end = max(end, interval.end) else: merged_intervals.append([start, end]) start = interval.start end = interval.end merged_intervals.append([start, end]) # add the last interval return merged_intervals
The key to solving problems like these is to draw out the possible arrangement of intervals in relation to each other and work through the scenarios.
Here's some more questions to put you to the test:
If you enjoyed this article, please go support the people over at https://www.educative.io/courses/grokking-the-coding-interview I've based this blog post on their content.