Merge Intervals

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].

/**

 * Definition for an interval.

 * struct Interval {

 *     int start;

 *     int end;

 *     Interval() : start(0), end(0) {}

 *     Interval(int s, int e) : start(s), end(e) {}

 * };

 */

class Solution {

public:

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

        vector<Interval> ans;

        if (intervals.size() == 0) {

            return ans;

        }

        sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start; });

        ans.push_back(intervals[0]);

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

            if (intervals[i].start <= ans.back().end) {

                ans.back().end = max(intervals[i].end, ans.back().end);

            } else {

                ans.push_back(intervals[i]);

            }

        }

        

        return ans;

    }

};

================ Recent attempt ==============
struct MyClass {
    bool operator()(vector<int> i, vector<int> j) {
        return (i[0] < j[0]);
    }
} comp;
class Solution {
public:

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> sol;
        if (intervals.size() < 2) {
            return intervals;
        }
        
        sort(intervals.begin(), intervals.end(), comp);
        
        int i = 0, k = 0;
        while (i < intervals.size() - 1) {
            vector<int> first = intervals[i];
            
            if (first[1] < intervals[i+1][0]) {
                sol.push_back(first);
                i++;
            } else {
                int first_val = first[0];
                int second_val = first[1];
                k = i + 1;
                while (k < intervals.size()) {
                    if (intervals[k][0] <= second_val) {
                        second_val = max(second_val, intervals[k][1]);
                    } else {
                        break;
                    }
                    k++;
                }
                vector<int> tmp;
                tmp.push_back(first_val);
                tmp.push_back(second_val);
                sol.push_back(tmp);
                i = k;
            }
        }
        if (k != intervals.size()) {
            sol.push_back(intervals.back());
        }
        return sol;
    }

};


=========== This time =======
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> sol;
        if (intervals.size() == 0) {
            return sol;
        }
        sort(intervals.begin(), intervals.end(),
             [](vector<int> first, vector<int> second) { return first[0] < second[0];});
        
        int start = intervals[0][0];
        int end = intervals[0][1];
        int iter = 1;
        while (iter < intervals.size()) {
            if (end >= intervals[iter][0]) {
                end = max(end, intervals[iter][1]);
            } else {
                sol.push_back(vector<int> {start, end});
                start = intervals[iter][0];
                end = intervals[iter][1];
            }
            iter++;
        }
        
        sol.push_back(vector<int> {start, end});
        return sol;
    }

};

========
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> output;
        if (intervals.size() == 0) {
            return output;
        }
        sort(intervals.begin(), intervals.end(), [](vector<int>& first,
                                                   vector<int>& second) {
            return first[0] < second[0];
        });
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] > end) {
                output.push_back({start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            } else {
                end = max(end, intervals[i][1]);
            }
        }
        output.push_back({start, end});
        return output;
    }

};