Easy C++ code Beats 100%


  • 0

    The idea is straight forward. We find the right place to insert the newInterval or combine it with the original intervals.

      vector<Interval> insert( vector<Interval>& intervals, Interval newInterval )
      {
        for (int i = 0; i<intervals.size(); ++i ) {
          //     ...         intervals[i].start ... intervals[i].end ...
          // newInterval.end ...
          if ( newInterval.end < intervals[i].start ) {
            intervals.insert( intervals.begin() + i, newInterval );
            return intervals;
          }
          //     ...         intervals[i].start ... intervals[i].end ...
          //                                                         newInterval.start ...
          else if ( newInterval.start > intervals[i].end )
            continue;
          else {
            int j = i;
            // find the last overlapping interval
            while ( i<intervals.size() && newInterval.end >= intervals[i].start )
              i++;
            intervals[j].start = min( newInterval.start, intervals[j].start );
            intervals[j].end = max( newInterval.end, intervals[i - 1].end );
            // copy the remainred intervals;
            while ( i<intervals.size() ) {
              intervals[++j] = intervals[i++];
            }
            intervals.resize( j + 1 );
            return intervals;
          }
        }
        intervals.push_back( newInterval );
        return intervals;
      }
    

Log in to reply
 

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