simple c++ solution(19ms)

  • 0
    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;
            return i.end < j.end;
    class Solution {
        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);
            return rst;

Log in to reply

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