题解 | #合并区间#

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类vector 
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        // write code here
        vector<Interval>merged;
        if(intervals.size()<=1)
        {
            return intervals;
        }
        //排序
        sort(intervals.begin(),intervals.end(),[](const Interval &a,const Interval &b){return a.start<b.start;});
        int first=0;
        for (int second = 1; second < intervals.size(); ++second) {  
            // 如果当前区间的起始位置小于等于前一个区间的结束位置，则合并这两个区间  
            if (intervals[second].start <= intervals[first].end) {  
                // 更新前一个区间的结束位置为两个区间结束位置中的较大者  
                intervals[first].end = max(intervals[first].end, intervals[second].end);  
            } else {  
                // 否则，将前一个区间加入合并后的结果中，并更新first为second  
                merged.push_back(intervals[first]);  
                first = second;  
            }  
        }  
  
        // 不要忘记将最后一个区间（如果有的话）也加入合并后的结果中  
        merged.push_back(intervals[first]);  
  
        return merged;  
    }
};

使用first和second进行遍历，模拟双指针，先进性排序，然后再使用second进行遍历，对比