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].
One basic idea is to construct the output array of merged intervals incrementally by traversing the input intervals. To achieve this, we iterate through each interval and check if it can be merged with any existing merged intervals in the output. If it cannot be merged, we include it as a separate interval in the output. How does this idea work? Let's explore!
Let's assume we have already merged intervals from index 0 to i - 1 in an output[] array. Now, for the ith interval, we traverse the output[] and check if the ith interval can be merged with any existing intervals in the output[]. If it cannot be merged, we add it to the output[]. Otherwise, we merge the ith interval with the overlapping interval in the output[].
To accomplish this, we use the merge function, which takes two intervals, X and Y, and verifies if they can be merged. In this function, we compare the end of interval X with the start of interval Y and vice versa. If the intervals do not overlap, we return false. However, if they overlap, we update the start of interval Y to the minimum of the two start points and the end of interval Y to the maximum of the two endpoints. Finally, we return true to indicate a successful merge.
struct Interval
{
int start;
int end;
Interval(int s, int e)
{
start = s;
end = e;
}
};
bool merge(Interval& X, Interval& Y)
{
if (X.end < Y.start || Y.end < X.start)
return false;
Y.start = min(X.start, Y.start);
Y.end = max(X.end, Y.end);
return true;
}
vector<Interval> mergeIntervals(vector<Interval>& intervals)
{
int n = intervals.size();
vector<Interval> output;
for (int i = 0; i < n; i = i + 1)
{
bool merged = false;
for (int j = 0; j < output.size(); j = i + 1)
{
if (merge(intervals[i], output[j]))
{
merged = true;
break;
}
}
if (!merged)
output.push_back(intervals[i]);
}
return output;
}
class Interval
{
public int start;
public int end;
public Interval(int s, int e)
{
start = s;
end = e;
}
}
public class IntervalMerger
{
private boolean merge(Interval X, Interval Y)
{
if (X.end < Y.start || Y.end < X.start)
return false;
Y.start = Math.min(X.start, Y.start);
Y.end = Math.max(X.end, Y.end);
return true;
}
public List<Interval> mergeIntervals(List<Interval> intervals)
{
int n = intervals.size();
List<Interval> output = new ArrayList<>();
for (int i = 0; i < n; i = i + 1)
{
boolean merged = false;
for (int j = 0; j < output.size(); j = j + 1)
{
if (merge(intervals.get(i), output.get(j)))
{
merged = true;
break;
}
}
if (!merged)
output.add(intervals.get(i));
}
return output;
}
}
class Interval:
def __init__(self, s, e):
self.start = s
self.end = e
def merge(X, Y):
if X.end < Y.start or Y.end < X.start:
return False
Y.start = min(X.start, Y.start)
Y.end = max(X.end, Y.end)
return True
def mergeIntervals(intervals):
n = len(intervals)
output = []
for i in range(n):
merged = False
for j in range(len(output)):
if merge(intervals[i], output[j]):
merged = True
break
if not merged:
output.append(intervals[i])
return output
We run nested loops where the outer loop runs n times, and the length of the inner loop depends on the size of the output array at given instance. During each iteration of the nested loop, we call the merge function only once, which takes O(1) time.
In the best-case scenario, if all intervals in the input are overlapping, the merge function will always return true, and the inner loop will break after one iteration. In this case, the inner loop will run only once. So the best-case time complexity is O(n).
In the worst-case scenario, if all intervals in the input are non-overlapping, the merge function will always return false and inner loop will run until the end. The total number of loop iterations is 1 + 2 + 3 + ... + n, which is equal to n(n + 1)/2. So the worst-case time complexity is O(n^2).
We are using constant extra space, so space complexity = O(1).
Now, the critical question is: Can we think of improving the time complexity? Can we perform some pre-processing to make merging easier? 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.