Sword finger offer II 074 Merge interval (sort, array)

Title Description

A simple merging interval problem . Subject portal

Their thinking

If the two intervals can be merged , There must be an intersection , That is, the head of the second interval is in the first interval , In this way, I thought of sorting all the intervals first , Then use an array tmp[] Record the starting point of the current interval . At the beginning, the starting point is set as the first interval intervals[0] The starting point of , Then traverse all the intervals ：

• If the current interval intervals[i] The starting point of tmp[0] and tmp[1] Between , That is, the merge interval with the current record tmp There is intersection , So merge the two intervals , hold tmp[1] Is changed to max(tmp[1], intervals[i][1])（ Here is the maximum of the two values , Easy to ignore ）;
• If the current interval intervals[i] The starting point is greater than tmp[1], That is, the merge interval with the current record tmp There is no intersection , that tmp Is an interval in the answer , Record in answer , And then tmp Update to the current interval intervals[i], Continue traversing .
• After the traversal is over , Put the interval tmp Record it in the answer .

Code

class Solution {
    
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
    
        vector<int> tmp(2);
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end(), [&](const vector<int>& a, const vector<int>& b) {
    
            return a[0] < b[0];
        }); //  Sort 
        for (int i = 0; i < intervals.size(); i++) {
    
            if (i == 0) {
    
                tmp = intervals[i]; // initialization tmp Section 
            }
            if (intervals[i][0] >= tmp[0] && intervals[i][0] <= tmp[1]) {
       // There is intersection 
                tmp[1] = max(tmp[1], intervals[i][1]);  //  Merge range 
            } else {
        // No intersection 
                ans.push_back(tmp); // Add answers 
                tmp = intervals[i];     // Reset tmp Section 
            }   
        }
        ans.push_back(tmp);
        return ans;
    }
};