My C++ O(n) time complexity method


  • 0
      vector<Interval> merge( vector<Interval>& intervals )
      {
        if ( intervals.size() <= 1 ) return intervals;
        // start_or_end save the point position and start or end imformation
        map<int, int> start_or_end;
        for ( const auto& in : intervals ) {
          start_or_end[in.start] ++;
          start_or_end[in.end] --;
        }
    
        vector<Interval> res;
        Interval inter( INT_MAX, INT_MIN );
        int cnt = 0;
        for ( const auto& se : start_or_end ) {
          // it is start point
          if ( se.second > 0) {
            inter.start = std::min( inter.start, se.first );
            cnt += se.second;
          }
          // it is end point
          else if ( se.second < 0) {
            cnt += se.second;
            inter.end = std::max( inter.end, se.first );
            if ( cnt == 0 ) {
              res.push_back( inter );
              inter.start = INT_MAX;
              inter.end = INT_MIN;
            }
          }
          // it is both start and end point
          else if( cnt == 0){
            res.push_back( Interval( se.first, se.first ) );
          }
        }
        return res;
      }
    

  • 0
    C

    Please provide explanation


  • 2
    A

    @yanchao_hust Unfortunately, the time complexity is not O(n) but O(nlogn).
    "map" is ordered, every insertion causes an implicit sort, which is O(nlogn).
    So it is no better than an explicit sort on the vector once for all.

    http://www.cplusplus.com/reference/map/map/insert/

    If N elements are inserted, Nlog(size+N)


Log in to reply
 

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