Union of Intervals

EPI 14.6

Description:

Merge Intervals的变种，interval有open和close end。

Example:

Note

Idea:

和merge interval的思想基本一样，如果下一个与当前最近一个不overlap，则进result，否则，考虑几种不同情况。

1. 后值大，直接进去
2. 后值小，不管
3. 值相同，则考虑几种情况：
   1. 前闭后开
   2. 前闭后闭
   3. 前开后闭
   4. 前开后开

是个比较好的design题目。

Code:

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

struct Edge{
    int val;
    bool isClosed;
    Edge(int v, bool isClosed): val(v), isClosed(isClosed) {}
};

struct Interval{
    Interval(Edge lft, Edge rht): left(lft), right(rht) {}

    Edge left, right;

    bool operator < (const Interval& rhs) const{
        if(left.val != rhs.left.val)
            return left.val<rhs.left.val;
        else {
            return left.isClosed; 
        }
    }
};

vector<Interval> unionInterval(vector<Interval> arr){
    if(arr.empty()) return {};

    sort(arr.begin(), arr.end());

    vector<Interval> result;
    result.push_back(arr[0]);

    for(int i=1; i<arr.size(); i++){
        // if not overlapping push in
        if(result.back().right.val< arr[i].left.val){
            result.push_back(arr[i]);
        }
        // if not overlapping push in
        else if(result.back().right.val == arr[i].left.val 
                && (!result.back().right.isClosed && !arr[i].left.isClosed) ){
            result.push_back(arr[i]);
        }
        else{ 
            // update the right value
            if(result.back().right.val < arr[i].right.val){
                result.back().right.val = arr[i].right.val;
                result.back().right.isClosed = arr[i].right.isClosed;
            }
            else if(result.back().right.val == arr[i].right.val) {
                if(!result.back().right.isClosed){
                    result.back().right.isClosed = arr[i].right.isClosed;
                }
            }
        }    

    }

    return result;
}

int main(){
    vector<Interval> arr;
    arr.push_back(Interval(Edge(12, true), Edge(14, true)));
    arr.push_back(Interval(Edge(0, false), Edge(3, false)));
    arr.push_back(Interval(Edge(1, true), Edge(2, true)));
    arr.push_back(Interval(Edge(3, true), Edge(4, false)));
    arr.push_back(Interval(Edge(2, true), Edge(4, true)));
    arr.push_back(Interval(Edge(5, true), Edge(7, false)));
    arr.push_back(Interval(Edge(7, true), Edge(8, false)));
    arr.push_back(Interval(Edge(8, true), Edge(11, false)));

    vector<Interval> result = unionInterval(arr);

    for(auto elem: result){
        cout<<elem.left.val<<' '<<elem.left.isClosed<<' ';
        cout<<elem.right.val<<' '<<elem.right.isClosed<<" >> ";
    }

}