32ms cpp solution


  • 0
    G

    explanation:

    1. sort despite the start time and end time.

    2. Start Time associate with value +1, end time associate with value -1

    3. loop over the sorted time array, when see a start time ++count, when see a end time --count. when count is 0, push the interval from first time to last time to the return result

      bool comparePoints(const pair<int, int>& point1, const pair<int, int>& point2) {
      return (point1.first < point2.first) ||
      (point1.first == point2.first && point1.second > point2.second);
      }

      vector<Interval> merge(vector<Interval>& intervals) {
      vector<Interval> ret;
      vector<pair<int, int> > points;
      for (auto& interval : intervals) {
      points.push_back(make_pair(interval.start, 1));
      points.push_back(make_pair(interval.end, -1));
      }
      sort(points.begin(), points.end(), comparePoints);
      int count = 0;
      Interval interval;
      for (int i=0; i<points.size(); ++i) {
      if(count == 0) {
      interval.start = points[i].first;
      }
      count += points[i].second;
      if(count == 0) {
      interval.end = points[i].first;
      ret.push_back(interval);
      }
      }
      return ret;
      }


Log in to reply
 

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