C++ 10 line solution. easing understanding


  • 85
    L
    vector<Interval> merge(vector<Interval>& ins) {
        if (ins.empty()) return vector<Interval>{};
        vector<Interval> res;
        sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});
        res.push_back(ins[0]);
        for (int i = 1; i < ins.size(); i++) {
            if (res.back().end < ins[i].start) res.push_back(ins[i]);
            else
                res.back().end = max(res.back().end, ins[i].end);
        }
        return res;
    }

  • 1
    S

    this is a really good solution. Another naive approach is to use the "insert interval function", which will result in o(n^2) time complexity.


  • 1
    J

    great work!I just want to know what does [](Interval a, Interval b){return a.start < b.start} mean? Is it a function point?


  • 0
    Y

    It's a lambda function introduced by C++ 11. It makes C++ looking like modern language.


  • 0
    K

    Great, I think the lambda compare function is very neat.


  • 0

    The another version:

        vector<Interval> merge(vector<Interval>& intervals) {
            sort(intervals.begin(), intervals.end(), [](Interval &a, Interval &b){return a.start < b.start;});
            vector<Interval> res;
            for (auto i : intervals) {
                if (res.empty() or res.back().end < i.start) res.push_back(i);
                else if (res.back().end >= i.start)
                    if (res.back().end < i.end)
                        res.back().end = i.end;
            }
            return res;
        }
    

  • 0
    Z

    Can anyone please help me to understand why changing "<" in comp function to "<=" gets "Time Limit Exceeded"? Thanks


  • 1
    F

    @zyydev "=" comp will led dead loop in sort function when some elements of vector are equal.


  • 1

    Very nice solution. I ended up doing a secondary sort on interval.end to achieve the same thing. For some reason this way is faster in JavaScript:

    var merge = function(intervals) {
        intervals.sort((a, b) => a.start === b.start ? a.end - b.end : a.start - b.start);
        const res = [];
        for (let i = 0; i < intervals.length; i++) {
            if (i < intervals.length - 1 && intervals[i].start === intervals[i + 1].start) continue;
            if (res.length && intervals[i].start > res[res.length - 1].end || !res.length) {
                res.push(intervals[i]);
            } else {
                res[res.length - 1].end = Math.max(res[res.length - 1].end, intervals[i].end);
            }
        }
        return res;
    };
    

  • 0
    T

    Thanks for sharing such nice and simple code.

    This is my solution, much more lines but also easy to understand:

    1. Sorted the input

    2. Comparing the contents (I separate into two case: A. Partially overlap B. Totally overlap)

    bool mySort (Interval a, Interval b)
    {
        return (a.start < b.start);
    }
    
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            if(intervals.empty())
            {
                return {};
            }
            //1. Sorting the interval with mySort funtion
            std::sort(intervals.begin(), intervals.end(), mySort);
            
            //2. Comparing
            Interval temp(intervals[0].start, intervals[0].end); //initailize
            vector<Interval> res;
            for(int i = 1; i < intervals.size(); ++i)
            {
                if(temp.end >= intervals[i].start)
                {
                    if(temp.end >= intervals[i].end) // totally overlap
                    {
                        continue;  //challenge the next 
                    }
                    else //partially overlap
                    {
                        temp.end = intervals[i].end; 
                        continue; //chanllenge the next
                    }
                }
                else
                {
                    res.push_back(temp);
                    temp.start = intervals[i].start; //update
                    temp.end = intervals[i].end;
                }
                
            }
            res.push_back(temp); // store the last one.
            return res;
        }
    };
    

  • 0
    I

    Sharing my solution:

    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            if (intervals.size() < 1) { return intervals; }
            
            sort(intervals.begin(), intervals.end(), [](const Interval& left, const Interval& right)
            {
                return left.start < right.start;
            });
            
            vector<Interval> res(1, intervals.front());
            
            for (size_t idx = 1; idx < intervals.size(); ++idx)
            {
                const auto& curr = intervals[idx];
                auto& last = res.back();
                
                if (last.end < curr.start)
                {
                    res.push_back(curr);
                }
                else
                {
                    last.end = max(last.end, curr.end);
                }
            }
            
            return res;
        }
    };
    

  • 0
    M

    Nice answer! Very clear and compact


  • 0
    E

    @lchen77 Had the same idea and almost the same code but it failed with Runtime Error when I submitted.


Log in to reply
 

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