Grokking the Coding Interview
Coding Interview Pattern: Merge Interval
How learning coding patterns makes interview preparation easy and efficient.
Being a pro at coding patterns makes life easier because we can quickly spot similarities between new problems and ones we’ve tackled before. This makes finding solutions a breeze.
One super important coding pattern to know is the Merge Interval. On is one of the most frequently occurring patterns in Coding Interviews. Let’s dive in and learn when and how to use it.
Merge Interval pattern describes an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, we either need to find overlapping intervals or merge intervals if they overlap.
Given two intervals (‘a’ and ‘b’), there will be six different ways the two intervals can relate to each other:
Understanding the above six cases will help us in solving all intervals related problems.
Let’s jump onto a coding problem to understand the Merge Interval pattern.
For a detailed discussion of these patterns and related problems with solutions, take a look at Grokking the Coding Interview.
Merge Intervals (medium)
Problem Statement
Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.
Example 1:
Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we
merged them into one [1,5].Example 2:
Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged
them into one [5,9].Example 3:
Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]
Explanation: Since all the given intervals overlap, we merged them
into one.Solution
Let’s take the example of two intervals (‘a’ and ‘b’) such that a.start <= b.start. There are four possible scenarios:
Our goal is to merge the intervals whenever they overlap. For the above-mentioned three overlapping scenarios (2, 3, and 4), this is how we will merge them:
The diagram above clearly shows a merging approach. Our algorithm will look like this:
- Sort the intervals on the start time to ensure
a.start <= b.start. - If ‘a’ overlaps ‘b’ (i.e.
b.start <= a.end), we need to merge them into a new interval ‘c’ such that:
c.start = a.start
c.end = max(a.end, b.end)3. We will keep repeating the above two steps to merge ‘c’ with the next interval if it overlaps with ‘c’.
Code
Here is what our algorithm will look like in Python (Jave solution right after it):
Python3
from __future__ import print_function
class Interval:
def __init__(self, start, end):
self.start = start
self.end = end
def print_interval(self):
print("[" + str(self.start) + ", " + str(self.end) + "]", end='')
def merge(intervals):
if len(intervals) < 2:
return intervals
# sort the intervals on the start time
intervals.sort(key=lambda x: x.start)
mergedIntervals = []
start = intervals[0].start
end = intervals[0].end
for i in range(1, len(intervals)):
interval = intervals[i]
if interval.start <= end: # overlapping intervals, adjust the 'end'
end = max(interval.end, end)
else: # non-overlapping interval, add the previous interval and reset
mergedIntervals.append(Interval(start, end))
start = interval.start
end = interval.end
# add the last interval
mergedIntervals.append(Interval(start, end))
return mergedIntervals
def main():
print("Merged intervals: ", end='')
for i in merge([Interval(1, 4), Interval(2, 5), Interval(7, 9)]):
i.print_interval()
print()
print("Merged intervals: ", end='')
for i in merge([Interval(6, 7), Interval(2, 4), Interval(5, 9)]):
i.print_interval()
print()
print("Merged intervals: ", end='')
for i in merge([Interval(1, 4), Interval(2, 6), Interval(3, 5)]):
i.print_interval()
print()
main()Java
import java.util.*;
class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
};
class Solution {
public static List<Interval> merge(List<Interval> intervals) {
if (intervals.size() < 2)
return intervals;
// sort the intervals by start time
Collections.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));
List<Interval> mergedIntervals = new LinkedList<Interval>();
Iterator<Interval> intervalItr = intervals.iterator();
Interval interval = intervalItr.next();
int start = interval.start;
int end = interval.end;
while (intervalItr.hasNext()) {
interval = intervalItr.next();
if (interval.start <= end) { // overlapping intervals, adjust the 'end'
end = Math.max(interval.end, end);
} else { // non-overlapping interval, add the previous interval and reset
mergedIntervals.add(new Interval(start, end));
start = interval.start;
end = interval.end;
}
}
// add the last interval
mergedIntervals.add(new Interval(start, end));
return mergedIntervals;
}
public static void main(String[] args) {
List<Interval> input = new ArrayList<Interval>();
input.add(new Interval(1, 4));
input.add(new Interval(2, 5));
input.add(new Interval(7, 9));
System.out.print("Merged intervals: ");
for (Interval interval : Solution.merge(input))
System.out.print("[" + interval.start + "," + interval.end + "] ");
System.out.println();
input = new ArrayList<Interval>();
input.add(new Interval(6, 7));
input.add(new Interval(2, 4));
input.add(new Interval(5, 9));
System.out.print("Merged intervals: ");
for (Interval interval : Solution.merge(input))
System.out.print("[" + interval.start + "," + interval.end + "] ");
System.out.println();
input = new ArrayList<Interval>();
input.add(new Interval(1, 4));
input.add(new Interval(2, 6));
input.add(new Interval(3, 5));
System.out.print("Merged intervals: ");
for (Interval interval : Solution.merge(input))
System.out.print("[" + interval.start + "," + interval.end + "] ");
System.out.println();
}
}Time Complexity
The time complexity of the above algorithm is O(N * logN), where ’N’ is the total number of intervals. We are iterating the intervals only once which will take O(N), in the beginning though, since we need to sort the intervals, our algorithm will take O(N * logN).
Space Complexity
The space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals. We will also need O(N) space for sorting. For Java, depending on its version, Collections.sort() either uses Merge sort or Timsort, and both these algorithms need O(N) space. Overall, our algorithm has a space complexity of O(N).
Similar Problems
Problem 1: Given a set of intervals, find out if any two intervals overlap.
Example:
Intervals: [[1,4], [2,5], [7,9]]
Output: true
Explanation: Intervals [1,4] and [2,5] overlap
Solution: We can follow the same approach as discussed above to find if any two intervals overlap.
Where to go from here
Learn more about the Merge Interval pattern in Grokking the Coding Interview.
Here are a few good posts on coding and system design interviews:
