Most efficient solution?


  • 0
    A

    My solution is very similar to the most popular proposed here, but I'd rather not use vector::erase, since it has to relocate and copy the whole vector (see http://www.cplusplus.com/reference/vector/vector/erase/). In the worst case, the vector may have to be relocated and copied every iteration (disjoint pairs mergeable intervals), thus hindering performance. Considering we are already consuming O(n) memory with the input, it is very likely that we can afford another O(n) memory, which will only be as large as the input in the worst case. Here is my proposal:

    class Solution {
        typedef Interval ITV;
        typedef vector<ITV> VITV;
        typedef vector<bool> VB;
    public:
        static VITV merge(VITV& intervals) {
            sort(intervals.begin(), intervals.end(), 
                [](const ITV& x, const ITV& y) { 
                    return x.start < y.start; 
            });
            int n = intervals.size();
            VITV merged;
            int i = 0;
            while (i < n) {
                int j = i;
                while (++i < n && intervals[i].start <= intervals[j].end)
                    intervals[j].end = max(intervals[j].end, intervals[i].end);
                merged.push_back(intervals[j]);
            }
            return merged;
        }
    };

Log in to reply
 

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