C++ 13ms solution with explanation in the code


  • 0
    C

    class Solution {
    public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {

        vector<Interval> result;
        if (intervals.empty()) {
            result.emplace_back(newInterval);
            return result;
        }
        
        bool startSettled = false, endSettled = false;
        for (int i = 0; i < intervals.size(); i++) {
            
            // CASE1: `start` is not settled
            // CASE1.1: if `start` is less than the current start, insert a new start
            if (!startSettled && newInterval.start < intervals[i].start) {
                startSettled = true;
                result.emplace_back(Interval(newInterval.start, newInterval.end));
                i--;
            }
            // CASE1.2: if `start` is greater than the current end
            else if (!startSettled && newInterval.start > intervals[i].end) {
                result.emplace_back(intervals[i]);
            }
            // CASE1.3: if `start` falls in the current interval
            else if (!startSettled) {
                startSettled = true;
                result.emplace_back(Interval(intervals[i].start, newInterval.end));
                i--;
            }
            
            // CASE2: `end` is not settled => currently result.back().end() == newInterval.end
            // CASE2.1: if `end` is less than the current start
            else if (!endSettled && newInterval.end < intervals[i].start) {
                endSettled = true;
                i--;
            }
            // CASE2.2: if `end` is greater than the current end, ignore the current interval
            else if (!endSettled && newInterval.end > intervals[i].end) continue;
            // CASE2.3: if `end` falls in the current interval
            else if (!endSettled) {
                endSettled = true;
                result.back().end = intervals[i].end;
            }
            else 
                result.emplace_back(intervals[i]);
        }
        if (startSettled == false)
            result.emplace_back(newInterval);
        return result;
    }
    

    };


Log in to reply
 

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