C++ 580ms solution sort first O(nlogn), then O(n) time, O(1) space


  • 2
    class Solution {
    public:
    static bool IntervalCompare(Interval &a, Interval &b){
        return (a.start<b.start);
    }
    vector<Interval> merge(vector<Interval>& intervals) {
        int k=intervals.size();
        if (k<=1) return intervals;
        sort(intervals.begin(),intervals.end(),IntervalCompare);
        vector<Interval> res;
        for (int i=0;i<k-1;i++){
            if (intervals[i].end>=intervals[i+1].end) {
                intervals[i+1].end = intervals[i].end;
                intervals[i+1].start = intervals[i].start;
            }
            else if (intervals[i].end>=intervals[i+1].start){
                intervals[i+1].start = intervals[i].start;
            }
            else res.push_back(intervals[i]);
        }
        res.push_back(intervals[k-1]);
        return res;
    }
    };

  • 1

    Neat solution, but its not O(1) space as its not done in-place.


  • 0

    Besides the output res, there is no other extra space. If this is not O(1), then there is no O(1) solution for all problem return a vector.


  • 1

    I agree, but O(1) is reserved for in-place solutions in general. For this problem, there is no O(1) solution as you stated.


  • 0
    R

    Saying "O(nlogn) first, then O(n)" doesn't make any sense.
    With the same logic, every solution to every problem can be stated in the form "O(...) first, then constant time"


  • 0

    @rmn The title accurately describes the time complexity of each major part of the codes. That is it.


Log in to reply
 

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