# Merge Intervals

Sep 24, 2023#leetcode#dsa

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:

• Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
• Output: [[1,6],[8,10],[15,18]]
• Explanation: In the input, the intervals [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.