[LeetCode] 56. Merge Intervals Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
This one is the same as the previous oneInsert IntervalVery similar. This question requires us to merge intervals. The previous question clearly stated that the input interval set is order, but this question does not. So the first thing we need to do is sort the interval set. Since we want to sort it is a structure, we need to define our own comparator to sort it with sort. We sort the start value from small to large. After sorting, we can start merging. First, save the first interval into the result, and then traverse the interval set from the second. If the last interval in the result has no overlap with the traversed current interval, directly store the current interval into the result. If there is overlap, update the end value of the last interval in the result to the larger value of the end and the current end value of the last interval in the result, and then continue to traverse the interval set, and so on to get the final result. The code is as follows:
Solution 1:
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (()) return {};
sort((), ());
vector<vector<int>> res{intervals[0]};
for (int i = 1; i < (); ++i) {
if (()[1] < intervals[i][0]) {
res.push_back(intervals[i]);
} else {
()[1] = max(()[1], intervals[i][1]);
}
}
return res;
}
};
The following solution stores the starting position and end position in two different arrays, starts and ends, and then sorts them respectively. Then, use two pointers i and j to initialize to point to the first position of the starts and ends array respectively. Then if i points to the last position in the starts array, or when the number on the starts array is greater than the number on the i+1 position of the ends array, it means that the interval is no longer continuous. Let's look at the example in the question. The sorted starts and ends are:
starts: 1 2 8 15
ends: 3 6 10 18
The position where red is i and the position where blue is j, then starts[i+1] is 8, ends[i] is 6, and 8 is greater than 6, so it is discontinuous at this time. Add the interval [starts[j], ends[i]], that is, [1, 6] to the result res, and then j is assigned to i+1 to continue the loop, see the code as follows:
Solution 2:
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = ();
vector<vector<int>> res;
vector<int> starts, ends;
for (int i = 0; i < n; ++i) {
starts.push_back(intervals[i][0]);
ends.push_back(intervals[i][1]);
}
sort((), ());
sort((), ());
for (int i = 0, j = 0; i < n; ++i) {
if (i == n - 1 || starts[i + 1] > ends[i]) {
res.push_back({starts[j], ends[i]});
j = i + 1;
}
}
return res;
}
};
There is another solution to this question. This solution directly calls the previous question.Insert Interval Since there are merge operations during the insertion process, we can create an empty set and insert each interval of the interval set into the result as a new interval, and we can also get the merged result. The four solutions in the question can be used here, but there is no need to list them all. Here we only select the solution 2 in the question and put it here. The code is as follows:
Solution three:
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
for (int i = 0; i < (); ++i) {
res = insert(res, intervals[i]);
}
return res;
}
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int> newInterval) {
vector<vector<int>> res;
int n = (), cur = 0;
for (int i = 0; i < n; ++i) {
if (intervals[i][1] < newInterval[0]) {
res.push_back(intervals[i]);
++cur;
} else if (intervals[i][0] > newInterval[1]) {
res.push_back(intervals[i]);
} else {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
}
}
(() + cur, newInterval);
return res;
}
};
This is the end of this article about C++ implementation of LeetCode (56. Merge interval). For more related content of C++ implementation of merge interval, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!