simple c++ solution(19ms)


  • 0
    B
    1. Sorting the input vector intervals;
    2. Insert first first sorted input element into result vector rst;
    3. Iterating the sorted input vector, if rst[-1].end>=intervals[i].start, means there are overlapping area between them, so merge the area by making rst[-1] to the max(intervals[i].end, rst[-1].end), otherwise, there are no overlapping area, just push intervals[i] in the back of rst.
    bool isSmaller(const Interval& i, const Interval& j)
    {
        if (i.start != j.start)
            return i.start < j.start;
        else
        {
            return i.end < j.end;
        }
    }
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            vector<Interval> rst;
            sort(intervals.begin(), intervals.end(), isSmaller);
            for (auto iter = intervals.begin(); iter != intervals.end(); ++iter)
            {
                if (rst.size() > 0 && iter->start <= rst.back().end)
                    rst.back().end = max(rst.back().end, iter->end);
                else
                    rst.push_back(*iter);
            }
            return rst;
        }
    
    };
    
    
    

Log in to reply
 

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