The Merge Intervals problem on LeetCode is a classic algorithmic problem that involves merging overlapping intervals. It’s a commonly used problem in job interviews and is a good exercise for practicing algorithmic thinking and array manipulation.
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
For example:
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]][1,3] and [2,6] overlap, so they are merged into [1,6]. The other two intervals [8,10] and [15,18] do not overlap with any other intervals, so they remain unchanged in the output.The goal is to take a list of intervals and combine any overlapping intervals into a single interval. This problem is often solved by first sorting the intervals based on their start times and then iterating through the sorted list to merge overlapping intervals.
Here’s solution in C++:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
vector<vector<int>> merge(vector<vector<int>> &intervals) {
// sort the intervals by their start time
sort(intervals.begin(), intervals.end());
// initialize the output array
vector<vector<int>> ans;
// initialize the current merged interval
vector<int> curr = intervals[0];
// iterate over the intervals
for (int i = 1; i < intervals.size(); i++) {
// if the current interval overlaps with the next one
if (curr[1] >= intervals[i][0]) {
// update the end time of the current merged interval
curr[1] = max(curr[1], intervals[i][1]);
} else {
// add the current merged interval to the output array
ans.push_back(curr);
// start a new merged interval with the next one
curr = intervals[i];
}
}
// add the last merged interval to the output array
ans.push_back(curr);
// return the output array
return ans;
}
int main() {
// Test cases with assertions
vector<vector<int>> intervals1 = {{1,3},{2,6},{8,10},{15,18}};
vector<vector<int>> result1 = merge(intervals1);
vector<vector<int>> expected1 = {{1,6},{8,10},{15,18}};
assert(result1 == expected1);
vector<vector<int>> intervals2 = {{1,4},{4,5}};
vector<vector<int>> result2 = merge(intervals2);
vector<vector<int>> expected2 = {{1,5}};
assert(result2 == expected2);
vector<vector<int>> intervals3 = {{1,2},{3,4},{5,6}};
vector<vector<int>> result3 = merge(intervals3);
vector<vector<int>> expected3 = {{1,2},{3,4},{5,6}};
assert(result3 == expected3);
vector<vector<int>> intervals4 = {{1,4},{0,4},{5,9}};
vector<vector<int>> result4 = merge(intervals4);
vector<vector<int>> expected4 = {{0,4},{5,9}};
assert(result4 == expected4);
cout << "All test cases passed!" << endl;
return 0;
}Time Complexity: Sorting the intervals based on their start times takes O(nlogn) time, where n is the number of intervals. Iterating through the sorted intervals once takes O(n) time since we process each interval exactly once. The dominant factor is the sorting step, so the overall time complexity is O(nlogn) due to the sorting operation.
The space complexity of the solution is O(n), where n is the number of intervals, as we use a new array mergedIntervals to store the merged intervals.