Leetcode: Merge Intervals: Analysis and solution in C++

PROBLEM:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Hide Tags

 Array Sort

Hide Similar Problems

 (H) Insert Interval

Analysis:

The main goal of this problem is to test your SORTing ability in coding. A general way to solve it is to sort it and then check one by one. It's common sense to sort the intervals in terms of the first item. 

1. How to sort a vector whose elements are a structure? SORT can be used to do the sorting but need to do some modifications on the STL of SORT. 
For basic knowledge of this part, please refer to the following reference:
Beginners guide to the std::sort() function

2. After the sorting, we need to check the merging intervals. All roads lead to Roma. You can use you own way to implement it.

What i'm using here is to create a 'result', and update the last value of result or push back a new value to result depends on the comparison result between 'result' and the current value form intervals.






//////////////////////////////////////////////////////////////////////////////////
// A complete codes for Merge Intervals in C++
/////////////////////////////////////////////////////////////////////////////////

class Solution {

       public:

              //define sort function

              struct compInterval {

                     bool operator()(const Interval &first, const Interval &second)const { return first.start < second.start; }

              };

       vector<Interval> merge(vector<Interval>& intervals) {

              vector<Interval> result;

        if (intervals.size() == 0)return result;

              //sort the intervals

              sort(intervals.begin(), intervals.end(), compInterval());

              result.push_back(intervals[0]);//initial value for result

              //check one by one

              for (int i = 1; i < intervals.size(); i++){

                     if (intervals[i].start<=(result.end()-1)->end){

                           //if pre.end<=cur.end, update; otherwise pass it!

                           if (intervals[i].end >= (result.end() - 1)->end){

                                (result.end() - 1)->end = intervals[i].end;

                           }

                     }

                     else{

                           result.push_back(intervals[i]);

                     }

              }

              return result;

       }

};