C++ inplace solution with O(nlgn) time complexity


  • 0
    C

    The idea is simple. After sorting the intervals based on their start times, apply the move zeroes inplace algorithm.

    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> res;
        auto comp = [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        };
        if (intervals.empty())
            return res;
        sort(intervals.begin(), intervals.end(), comp);
        int start = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[start].end < intervals[i].start) {
                start++;
                intervals[start] = intervals[i];
            }
            else {
                intervals[start].end = max(intervals[start].end, intervals[i].end);
            }
        }
        int orig_size = intervals.size();
        for (int i = 0; i < orig_size - start - 1; i++)
            intervals.pop_back();
        return intervals;
    }
    

Log in to reply
 

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