Share my O(n) solution - 13 lines


  • -3
    Q
    bool operator < (const Interval &a, const Interval &b) {return a.start < b.start;}
    class Solution {
    public:
        vector<Interval> merge(vector<Interval> &ins) {
            if(!ins.size()) return ins;
            sort(ins.begin(), ins.end());
            int l = ins[0].start, r = ins[0].end;
            vector<Interval> res;
            for(int i = 1; i < ins.size(); i++) {
                if(ins[i].start <= r) r = max(r, ins[i].end);
                else {
                    res.push_back(Interval(l, r));
                    l = ins[i].start, r = ins[i].end;
                }
            }
            res.push_back(Interval(l, r));
            return res;
        }
    };
    

    Alright, it's 13 lines in the main function :) The idea is to sort intervals according to their start position. while the next interval could be merged, we only end position of the current interval.


  • 17
    L

    When you sort, it's already O(n logn), isn't it?


Log in to reply
 

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