Interval List Intersections Solutions in C++

// Source : https://leetcode.com/problems/interval-list-intersections/
// Author : Hao Chen
// Date   : 2019-02-05



/**
 * 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:
    //return true if lhs starts earlier than  rhs
    bool compareInterval(Interval& lhs, Interval& rhs) {
        return lhs.start < rhs.start;
    }
    //check two interval overlapped or not
    bool overlapped(Interval& lhs, Interval& rhs) {
        return (compareInterval(lhs, rhs)) ?
                             lhs.end >= rhs.start:
                             rhs.end >= lhs.start;

    }
    //merge two interval - return the intersections of two intervals
    Interval mergeTwoInterval(Interval& lhs, Interval& rhs) {
        Interval result;
        result.start = max(lhs.start, rhs.start);
        result.end = min(lhs.end, rhs.end);
        return result;
    }

    vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {
        int lenA = A.size();
        int lenB = B.size();

        vector<Interval> result;
        if (lenA <=0 || lenB<=0) return result; //edge case

        int i=0, j=0;
        while ( i < lenA && j < lenB ) {
            if( overlapped(A[i], B[j]) ) {
                result.push_back(mergeTwoInterval(A[i], B[j]));
                // if the current interval is not overlapped with next one,
                // then we move the next interval.
                int nexti = i;
                if ( j==lenB-1 || !overlapped(A[i], B[j+1]) ) nexti=i+1;
                if ( i==lenA-1 || !overlapped(A[i+1], B[j]) ) j++;
                i = nexti;
            }else{
                //if not overlapped, we just move the next one
                compareInterval(A[i], B[j]) ? i++ : j++;
            }
        }
        return result;
    }
};

/// Source : https://leetcode.com/problems/interval-list-intersections/
/// Author : liuyubobobo
/// Time   : 2019-02-04

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


/// Ad-Hoc
/// Time Complexity: O(m + n)
/// Space Complexity: O(1)

/// 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> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {

        vector<Interval> res;

        int i = 0, j = 0;
        while(i < A.size() && j < B.size()){

            int l = max(A[i].start, B[j].start);
            int h = min(A[i].end, B[j].end);
            if(l <= h)
                res.push_back(Interval(l, h));

            if(A[i].end <= B[j].end)
                i ++;
            else
                j ++;
        }
        return res;
    }
};


void print_vec(const vector<Interval>& vec){

    for(const Interval& interval: vec)
        cout << "(" << interval.start << "," << interval.end << ") ";
    cout << endl;
}

int main() {

    vector<Interval> A1 = {Interval(0,2),Interval(5,10),Interval(13,23),Interval(24,25)};
    vector<Interval> B1 = {Interval(1,5),Interval(8,12),Interval(15,24),Interval(25,26)};
    print_vec(Solution().intervalIntersection(A1, B1));
    // [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

    vector<Interval> A2 = {Interval(5,10)};
    vector<Interval> B2 = {Interval(5,10)};
    print_vec(Solution().intervalIntersection(A2, B2));
    // [[5, 10]]

    vector<Interval> A3 = {Interval(3,5), Interval(9, 20)};
    vector<Interval> B3 = {Interval(4,5), Interval(7, 10), Interval(11, 12), Interval(14, 15), Interval(16, 20)};
    print_vec(Solution().intervalIntersection(A3, B3));
    // [[4,5],[9,10],[11,12],[14,15],[16,20]]

    return 0;
}