C++11 O(N*log(N)) solution, input data preserved


  • 0
    X

    The idea is to sort the intervals by left end, then going from left to right join the intervals while each next interval intersects with the one being currently merged. Some people have shared different variations of this approach. Here is mine, which doesn't affect the input data.

    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> result;
        if(intervals.empty())
        {
            return result;
        }
        result.resize(intervals.size());
        copy(intervals.begin(), intervals.end(), result.begin());
        sort(result.begin(), result.end(), [](const Interval& lhs, const Interval& rhs){
            return (lhs.start < rhs.start) || ((lhs.start == rhs.start) && lhs.end < rhs.end);
        });
        
        size_t iMergeStart = 0;
        for(size_t i = 1; i < result.size(); ++i)
        {
            while((i < result.size()) && (result[iMergeStart].end >= result[i].start))
            {
                if(result[iMergeStart].end < result[i].end)
                {
                    result[iMergeStart].end = result[i].end;
                }
                ++i;
            }
            if(i < result.size())
            {
                swap(result[++iMergeStart], result[i]);
            }
        }
        result.resize(iMergeStart + 1);
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.