56. Merge Intervals (Array; Project)

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.empty() || intervals.size() == 1) return intervals;
        for(vector<Interval>::iterator it = intervals.begin()+1; it < intervals.end();it++)
        {
            for(vector<Interval>::iterator innerIt = intervals.begin(); innerIt < it;innerIt++)
            {
                int left = min(it->start, innerIt->start);
                int right = max(it->end, innerIt->end);
                int size1 = (it->end) - (it->start);
                int size2 = (innerIt->end) - (innerIt->start);
                if(right - left > size1 + size2) //求线段是否重叠：比较投影的左右端点间长度与线段长度和
                    continue;
                else
                {
                    innerIt->start = left;
                    innerIt->end = right;
                    intervals.erase(it);
                    it = innerIt;
                    break;
                }
            }
        }
        return intervals;
    }
};