C++ Solution Sort start first Easy to understand


  • 0
    C
    • use c++ costumed compare function cmp to compare the start index and sort the input vector intervals
    • keep a temporary Interval struct tmp to merge the input. ie. if the next Interval it->end is bigger than tmp.end, we extend the end index.

    • push the tmp to return vector<Interval> if it->start is larger than previous tmp.end.

    • make sure push back the last tmp and return the result.

      class Solution {
      public:
      static bool cmp(const Interval& a, const Interval& b)
      {
      return a.start < b.start;
      }

       vector<Interval> merge(vector<Interval>& intervals) 
       {
           vector<Interval> ret;
           Interval tmp;
           
           if (intervals.empty())
           {
               return ret;
           }
           
           sort(intervals.begin(), intervals.end(), cmp);
           
           tmp.start = intervals[0].start;
           tmp.end = intervals[0].end;
           
           for (auto it = intervals.begin()+1; it != intervals.end(); it++)
           {
               if (it->start <= tmp.end)
               {
                   if (it->end > tmp.end)
                   {
                       tmp.end = it->end;
                   }
               }
               else
               {
                   ret.push_back(tmp);
                   
                   tmp.start = it->start;
                   tmp.end = it->end;
               }
           }
           
           ret.push_back(tmp);
           
           return ret;
       }
      

      };


Log in to reply
 

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