C++ O(N) solution, well structured with extracted "addRight" method


  • 0

    Extract method addRight to make the code simpler.

    NOTE: You have to take advantage that the given inters are already sorted to achieve O(N) time.

        vector<Interval> insert(vector<Interval>& inters, Interval j) {
            vector<Interval> res;
            
            bool added = false;
            for (auto& i : inters) {
                if (!added and i.start > j.start) 
                    addRight(res, j), added = true;
                addRight(res, i);
            }
            if (!added) addRight(res, j);
            return res;
    
        }
        
        // Added right interval j to the sorted inters: O(1) time
        void addRight(vector<Interval>& inters, Interval j) {
            if (inters.empty() or inters.back().end < j.start) inters.push_back(j);
            else inters.back().end = max(inters.back().end, j.end);
        }
    

Log in to reply
 

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