Merge Intervals Solutions in C++

// Source : https://oj.leetcode.com/problems/merge-intervals/
// Author : Hao Chen
// Date   : 2014-08-26



#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

//Two factos sorting [start:end]
bool compare(const Interval& lhs, const Interval& rhs){
    return (lhs.start==rhs.start) ? lhs.end < rhs.end : lhs.start < rhs.start;
}

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

    vector<Interval> result;

    if (intervals.size() <= 0) return result;
    //sort the inervals. Note: using the customized comparing function.
    sort(intervals.begin(), intervals.end(), compare);
    for(int i=0; i<intervals.size(); i++) { 
        int size = result.size();
        // if the current intervals[i] is overlapped with previous interval.
        // merge them together
        if( size>0 && result[size-1].end >= intervals[i].start) {
            result[size-1].end = max(result[size-1].end, intervals[i].end); 
        }else{
            result.push_back(intervals[i]);
        }
    }
    
    return result;
}


int main(int argc, char**argv)
{
    Interval i1(1,4);
    Interval i2(0,2);
    Interval i3(3,5);
    Interval i4(15,18);
    vector<Interval> intervals;
    intervals.push_back(i1);
    intervals.push_back(i2);
    intervals.push_back(i3);
    intervals.push_back(i4);
    
    vector<Interval> r = merge(intervals);
    
    for(int i=0; i<r.size(); i++){
        cout << "[ " << r[i].start << ", " << r[i].end << " ] ";
    }
    cout <<endl;

    return 0;
}

#include <vector>
using std::vector;
#include <algorithm>

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> ret;
        std::sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b){
            return a.start < b.start;
        });
        for (const auto &interval : intervals) {
            if (!ret.empty() && interval.start <= ret.back().end)
                ret.back().end = std::max(interval.end, ret.back().end);
            else ret.push_back(interval);
        }
        return ret;
    }
};

/// Source : https://leetcode.com/problems/merge-intervals/description/
/// Author : liuyubobobo
/// Time   : 2017-11-15
/// Updated: 2019-05-23

#include <iostream>
#include <vector>

using namespace std;


/// Sorting
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        if(intervals.size() <= 1)
            return intervals;

        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            if(a[0] != b[0])
                return a[0] < b[0];
            return a[1] < b[1];
        });

        vector<vector<int>> res;
        res.push_back(intervals[0]);
        for(int i = 1 ; i < intervals.size() ; i ++){
            if(cross(res.back(), intervals[i])){
                vector<int> newInterval = mergeInterval(res.back(), intervals[i]);
                res.pop_back();
                res.push_back(newInterval);
            }
            else
                res.push_back(intervals[i]);
        }

        return res;
    }

private:
    bool cross(const vector<int>& interval1, const vector<int>& interval2){
        return interval2[0] <= interval1[1];
    }

    vector<int> mergeInterval(const vector<int>& interval1, const vector<int>& interval2){
        return {min(interval1[0], interval2[0]), max(interval1[1], interval2[1])};
    }
};


void printIntervals(const vector<vector<int>>& vec){
    for(const vector<int>& interval: vec)
        cout << interval[0] << " " << interval[1] << endl;
    cout << endl;
}

int main() {

    vector<vector<int>> vec1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    printIntervals(Solution().merge(vec1));
    // [1,6] [8,10] [15,18]

    // ---

    vector<vector<int>> vec2 = {{1, 4}, {0, 0}};
    printIntervals(Solution().merge(vec2));
    // [0,0] [1,4]

    return 0;
}