A 16ms C++ Solution with Comments


  • 0
    Y
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            // Insert the newInterval into right position according to start
            int i = 0;
            for(i = 0; i < intervals.size(); i++) {
                if(newInterval.start < intervals[i].start) {
                    intervals.insert(intervals.begin() + i, newInterval);
                    break;
                }
            }
            if(i == intervals.size()) intervals.push_back(newInterval);
            
            // Merge the overlap Interval
            Interval* temp = &intervals[0];
            for(int j = 1; j < intervals.size(); j++) {
                // Find the interval that need to merge
                if(temp->end < intervals[j].start) temp = &intervals[j];
                else if((temp->end >= intervals[j].start)&&(temp->end <=intervals[j].end)) {
                    // If the end of the interval we want to merge is within one of the interval, merge 
                    // these two into the first one and mark the second interval.
                    temp->end = intervals[j].end;
                    intervals[j].start = -1;
                    intervals[j].end = -1;
                } else if(temp->end > intervals[j].end) {
                    // If an interval is within the range of the interval we want to merge, marker it.
                    intervals[j].start = -1;
                    intervals[j].end = -1;
                }
            }
            
            // Get result
            vector<Interval> res;
            // Get the intervals without marks.
            for(int n = 0; n < intervals.size(); n++) {
                if(intervals[n].start != -1) res.push_back(intervals[n]);
            }
            return res;
        }
    };

Log in to reply
 

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