The key to solving this problem is to first sort the intervals based on the starting time. Once sorted, we can iterate over the intervals and merge them if they overlap. Two intervals overlap if the start of the current interval is less than or equal to the end of the previous interval.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), required for the output array.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5vector<vector<int>> merge(vector<vector<int>>& intervals) {
6 if (intervals.empty()) return {};
7 sort(intervals.begin(), intervals.end());
8 vector<vector<int>> merged;
9 merged.push_back(intervals[0]);
10 for (const auto& interval : intervals) {
11 if (merged.back()[1] >= interval[0]) {
12 merged.back()[1] = max(merged.back()[1], interval[1]);
13 } else {
14 merged.push_back(interval);
15 }
16 }
17 return merged;
18}In C++, the sort function is utilized to sort intervals based on the starting time. A single pass through the intervals allows us to merge them where necessary.
Another approach involves consecutive comparisons and inserting intervals into a new list if they do not overlap with the current interval being processed.
Time Complexity: O(n log n).
Space Complexity: O(n).
1var merge = function(intervals) {
2 intervals.sort((a, b) => a[0] - b[0]);
3 let merged = [];
4 intervals.forEach(interval => {
5 if (!merged.length || merged[merged.length - 1][1] < interval[0]) {
6 merged.push(interval);
7 } else {
8 merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
9 }
10 });
11 return merged;
12};In JavaScript, intervals undergo sorting followed by a check to see if the latest one overlaps and needs merging with existing segments in a new combined list.