Merge Overlapping Intervals
Difficulty: Medium, Asked-in: Amazon, Adobe, Hike
Key takeaway: An excellent problem to learn problem solving using sorting.
Let’s understand the problem
Given an array of intervals where the start and end points of each interval are provided, write a program to merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.
- The output should be an array of only mutually exclusive intervals.
- The intervals can be given in any order.
More examples
Input: intervals = [ [9, 12], [3, 7], [1, 4], [14, 17] ], Output: [ [1, 7], [9, 12], [14, 17] ]
Explanation: Since intervals [1, 4] and [3, 7] are overlapping, we merge them into [1, 7].
Input: intervals = [ [1, 6], [6, 9] ], Output: [ [1, 9] ]
Explanation: Intervals [1, 6] and [6, 9] are overlapping.
Input: intervals = [ [8, 10], [2, 4], [1, 3], [5, 9] ], Output: [ [1, 4], [5, 10]]
Explanation: Intervals [2, 4] and [1, 3] are overlapping, we merge them into [1, 4]. Similarly, we merge [8, 10] and [5, 9] into [5, 10].
Using sorting and stack data structure
Solution idea
The idea is to sort the intervals based on their start times and then merge them iteratively using a stack. Here, sorting will help us easily identify the overlapping intervals, and the stack will help us keep track of the merged intervals.
Solution steps
- We create an output array to store merged intervals.
- We sort the intervals based on their start times.
-
Now, we create a stack to store intervals and run a loop to access each interval.
- If the stack is empty or the top interval in the stack does not overlap with the current interval, we push the current interval into the stack. Note: An interval will not overlap if the end of the interval at the top of the stack is less than the start of the current interval.
- If the top interval of the stack overlaps with the current interval, we merge both intervals by updating the end of the top interval with the end of the current interval. Note: An interval will overlap if the end of the interval at the top of the stack is less than the end of the current interval.
- After processing all intervals, all merged intervals will be present inside the stack. We iterate over the stack and insert the intervals at the end of the output[] array.
- Finally, we return the output[] array.
Solution code C++
bool compareIntervals(const Interval& a, const Interval& b)
{
return a.start < b.start;
}
vector<Interval> mergeIntervals(vector<Interval>& intervals)
{
int n = intervals.size();
stack<Interval> s;
vector<Interval> output;
sort(intervals.begin(), intervals.end(), compareIntervals);
for (int i = 0; i < n; i = i + 1)
{
Interval curr = intervals[i];
if (s.empty() || s.top().end < curr.start)
s.push(curr);
else if (s.top().end < curr.end)
s.top().end = curr.end;
}
while (!s.empty())
{
output.push_back(s.top());
s.pop();
}
return output;
}Solution code Java
class Solution
{
public static int compareIntervals(Interval a, Interval b)
{
if(a.start < b.start)
return 1;
else
return 0;
}
public static List<Interval> mergeIntervals(List<Interval> intervals)
{
int n = intervals.size();
Stack<Interval> stack = new Stack<>();
List<Interval> output = new ArrayList<>();
intervals.sort(Solution::compareIntervals);
for (int i = 0; i < n; i = i + 1)
{
Interval curr = intervals.get(i);
if (stack.isEmpty() || stack.peek().end < curr.start)
stack.push(curr);
else if (stack.peek().end < curr.end)
stack.peek().end = curr.end;
}
while (!stack.isEmpty())
{
output.add(stack.peek());
stack.pop();
}
return output;
}
}Solution code Python
def compareIntervals(a, b):
return a.start < b.start
def mergeIntervals(intervals):
intervals.sort(key=lambda x: x.start)
stack = []
output = []
for i in range(len(intervals)):
curr = intervals[i]
if not stack or stack[-1].end < curr.start:
stack.append(curr)
elif stack[-1].end < curr.end:
stack[-1].end = curr.end
while stack:
output.append(stack[-1])
stack.pop()
return outputTime and space complexity analysis
We are sorting the interval and running a single loop to merge intervals using stack. Suppose we are using some efficient O(nlogn) sorting algorithm like quick sort, merge sort or heap sort.
At each iteration of the single loop, we are doing O(1) operation to merge intervals. So overall time complexity = Time complexity of sorting + O(n)*O(1) = O(nlogn) + O(n) = O(nlogn).
Space complexity depends on the implementation of the sorting algorithm and the size of the stack. In the worst case, the size of the stack will be O(n) when all intervals are non-overlapping (Think!) If we use merge sort, then space complexity = O(n) + O(n) = O(n). If we use heap sort, then space complexity = O(1) + O(n) = O(n).
Using the sorting and single scan
The above solution requires O(n) additional space for the stack. How can we solve this problem without using a stack? Here is an observation: If we sort the intervals based on their start values, we can easily identify and merge overlapping intervals in a single scan. The idea is simple: Sorting ensures that overlapping intervals are adjacent to each other.
Solution steps
- We declare an array output[] to store the merged intervals.
- We sort the intervals based on their start values.
- We also initialize a variable currInterval with the first interval to track the current interval.
- Now we iterate through the sorted intervals starting from the second interval and compare the end value of the currInterval with the start value of the next interval.
- If there is an overlap (currInterval.end >= intervals[i].start), we update the end value of currInterval with max(currInterval.end, intervals[i].end). This will extend the merged interval. If there is no overlap, we add currInterval to the output[] and update the currInterval with the next interval.
- After iterating through all intervals, we add the final currInterval to the output since it represents the last merged interval. Finally, we return the output[].
Solution code C++
bool compareIntervals(const Interval& a, const Interval& b)
{
return a.start < b.start;
}
vector<Interval> mergeIntervals(Interval intervals[], int n)
{
vector<Interval> output;
sort(In, In + n, compareIntervals);
Interval currInterval = intervals[0];
for (int i = 1; i < n; i = i + 1)
{
if (currInterval.end >= intervals[i].start)
currInterval.end = max(currInterval.end, intervals[i].end);
else
{
output.push_back(currInterval);
currInterval = intervals[i];
}
}
output.push_back(currInterval);
return output;
}Solution code Java
class Solution
{
public static List<Interval> mergeIntervals(Interval[] intervals, int n)
{
List<Interval> output = new ArrayList<>();
Arrays.sort(intervals, 0, n, Comparator.comparingInt(a -> a.start));
Interval currInterval = intervals[0];
for (int i = 1; i < n; i = i + 1)
{
if (currInterval.end >= intervals[i].start)
currInterval.end = Math.max(currInterval.end, intervals[i].end);
else
{
output.add(currInterval);
currInterval = intervals[i];
}
}
output.add(currInterval);
return output;
}
}Solution code Python
def compareIntervals(a, b):
return a.start < b.start
def mergeIntervals(intervals, n):
output = []
intervals.sort(key=lambda x: x.start)
currInterval = intervals[0]
for i in range(1, n):
if currInterval.end >= intervals[i].start:
currInterval.end = max(currInterval.end, intervals[i].end)
else:
output.append(currInterval)
currInterval = intervals[i]
output.append(currInterval)
return outputTime and space complexity analysis
We are sorting the intervals and running a single loop. Suppose we are using an efficient O(nlogn) sorting algorithm like quicksort, merge sort, or heapsort. At each iteration of the single loop, we perform an O(1) operation to merge intervals. So overall time complexity = Time complexity of sorting + O(n)*O(1) = O(nlogn) + O(n) = O(nlogn).
The space complexity depends on the implementation of the sorting algorithm. If we use merge sort, then the space complexity is O(n). If we use heapsort, then the space complexity is O(1).
In-place solution using sorting and single loop
Solution idea
The idea here is to sort the intervals based on the start time and modify the same input array to store the merged intervals. To achieve this, we maintain an index variable to track the index of the last merged interval. We update the start and end points of the new interval based on the interval present at the index.
Solution steps
- We sort all intervals in increasing order of the start time.
- We initialize an index variable to keep track of the last merged interval in the same input array. Now we traverse the sorted intervals from the second interval up to the last interval.
- In each iteration, we check if the current interval (intervals[i]) overlaps with the interval at intervals[index]. If there is an overlap, i.e., the end of the interval at intervals[index] is greater than or equal to the start of the interval at intervals[i].
- For merging, we update the end of the interval at intervals[index] to max (intervals[index].end, intervals[i].end) and the start to min (intervals[index].start, intervals[i].start).
- If there is no overlap, we increment the index and copy the current interval to the next position in the array (intervals[index] = intervals[i]).
- After iterating through all the intervals, we return the length of the merged intervals, which is index + 1.
Solution code C++
bool compareIntervals(const Interval& a, const Interval& b)
{
return a.start < b.start;
}
int mergeIntervals(Interval intervals[], int n)
{
int index = 0;
sort(intervals, intervals + n, compareIntervals);
for (int i = 1; i < n; i = i + 1)
{
if (intervals[index].end >= intervals[i].start)
{
intervals[index].end = max(intervals[index].end, intervals[i].end);
intervals[index].start = min(intervals[index].start, intervals[i].start);
}
else
{
index = index + 1;
intervals[index] = intervals[i];
}
}
return index + 1;
}
void printIntervals(Interval intervals[], int index)
{
for (int i = 0; i < index; i = i + 1)
cout << "[" << intervals[i].start << ", " << intervals[i].end << "] ";
cout << endl;
}Solution code Java
class Solution
{
public static int mergeIntervals(Interval[] intervals, int n)
{
int index = 0;
Arrays.sort(intervals, 0, n, Comparator.comparingInt(a -> a.start));
for (int i = 1; i < n; i = i + 1)
{
if (intervals[index].end >= intervals[i].start)
{
intervals[index].end = Math.max(intervals[index].end, intervals[i].end);
intervals[index].start = Math.min(intervals[index].start, intervals[i].start);
}
else
{
index = index + 1;
intervals[index] = intervals[i];
}
}
return index + 1;
}
public static void printIntervals(Interval intervals[], int index)
{
for (int i = 0; i < index; i = i + 1)
System.out.println("[" + intervals[i].start + ", " + intervals[i].end + "] ");
System.out.println();
}
}Solution code Python
def mergeIntervals(intervals, n):
intervals.sort(key=lambda x: x.start)
index = 0
for i in range(1, n):
if intervals[index].end >= intervals[i].start:
intervals[index].end = max(intervals[index].end, intervals[i].end)
intervals[index].start = min(intervals[index].start, intervals[i].start)
else:
index = index + 1
intervals[index] = intervals[i]
return index + 1Time and space complexity analysis
We are sorting the interval and running a single loop to merge intervals. So overall time complexity = Time complexity of sorting + O(n)*O(1) = O(nlogn) + O(n) = O(nlogn).
Since we store the merged intervals in the same input array, the space complexity depends only on the sorting algorithm used. If we use merge sort, the space complexity is O(n). If we use heap sort, the space complexity is O(1).
Critical idea to think!
- In the third solution, when (currInterval.end >= intervals[i].start), we merge the endpoints of intervals. Why are we not considering the condition for the start time?
- In the stack-based approach, what is the count of push and pop operations in the worst case?
- Can we think of solving this problem using a data structure like a hash table or a binary search tree?
- Can we think of solving this problem using a graph or a disjoint set data structure?
Suggested coding questions to practice
- Given a set of non-overlapping intervals and a new interval, insert the interval into the intervals and merge if necessary.
- Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
- Given an array of meeting time intervals, find the minimum number of conference rooms required.
- Given a list of intervals, find the maximum number of intervals that overlap at any point in time.
- Given a list of intervals, remove the intervals that are completely covered by another interval in the list.
- Given a set of intervals, for each interval, find the interval with the smallest start time that overlaps with it.
- Given two lists of closed intervals, return their intersection.
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!