EPI 14.6

# Description:

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

## Example:

``````Note
``````

# Idea:

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

# 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<<" >> ";
}

}
``````