Difficulty: Medium, Asked-in: Amazon, Adobe, Hike
Key takeaway: An excellent problem to learn problem solving using sorting.
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.
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].
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.
Now, we create a stack to store intervals and run a loop to access each interval.
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;
}
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;
}
}
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 output
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).
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.
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;
}
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;
}
}
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 output
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).
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.
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;
}
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();
}
}
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 + 1
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).
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.