Easy O(n) solution in C++


  • 1
    R

    just find the place of new interval and add it, or update it

    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval t) {
            vector<Interval> result; 
            int i=0;
            bool t_added=false;
            for(i=0; i<intervals.size(); ++i) {
                if(intervals[i].end<t.start)
                    result.push_back(intervals[i]);
                else if(intervals[i].start > t.end){
                    result.push_back(t);
                    t_added=true;
                    break;
                }
                else { //update t 
                    t.start=min(t.start, intervals[i].start);
                    t.end=max(t.end, intervals[i].end);
                }
            }
            if(!t_added) result.push_back(t);
            for(; i<intervals.size(); ++i){
                result.push_back(intervals[i]);
            }
            return result;
        }
    };

  • 0
    F
    This post is deleted!

Log in to reply
 

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