#include <iostream>
#include <utility>
#include <list>
template<class T>
struct traits_interval
{
typedef T value_type;
};
template<class T>
class interval
{
public :
typedef typename traits_interval<T>::value_type value_type;
interval() : pinterval(std::make_pair(T(), T())) {}
interval(const T& start, const T& end) : pinterval(std::make_pair(start, end)){}
T& start() { return pinterval.first; }
const T& start() const { return pinterval.first; }
T& end() { return pinterval.second; }
const T& end() const { return pinterval.second; }
friend bool operator<(const interval<T>& first, const interval<T>& second)
{
if(first.start() == second.start()) return first.end() < second.end();
return first.start() < second.start();
}
private :
std::pair<T, T> pinterval;
};
namespace
{
typedef std::list<interval<int>> linterval;
typedef std::list<interval<int>>::iterator iinterval;
}
class merge_overlapping_intervals
{
public :
void operator()(std::list<interval<int>>& intervals)
{
intervals.sort();
iinterval inext(intervals.begin()); ++inext;
for(iinterval i(intervals.begin()), iend(intervals.end()); inext != iend;)
{
if((i->end() > inext->start()))
{
if(i->end() >= inext->end()) intervals.erase(inext++);
else if(i->end() < inext->end())
{ i->end() = inext->end(); intervals.erase(inext++); }
}
else { ++i; ++inext; }
}
}
};
int main()
{
linterval intervals{interval<int>(5, 8), interval<int>(3, 6), interval<int>(1, 4), interval<int>(8, 9)};
merge_overlapping_intervals()(intervals);
for(interval<int> i : intervals) std::cout << " {" << i.start() << ", " << i.end() << "}";
std::cout << "\n";
linterval intervals_2{interval<int>(3, 4), interval<int>(3, 6), interval<int>(1, 4)};
merge_overlapping_intervals()(intervals_2);
for(interval<int> i : intervals_2) std::cout << " {" << i.start() << ", " << i.end() << "}";
std::cout << "\n";
linterval intervals_3{interval<int>(1, 4), interval<int>(1, 6), interval<int>(1, 4)};
merge_overlapping_intervals()(intervals_3);
for(interval<int> i : intervals_3) std::cout << " {" << i.start() << ", " << i.end() << "}";
std::cout << "\n";
linterval intervals_4{interval<int>(3, 6), interval<int>(1, 2), interval<int>(7, 8)};
merge_overlapping_intervals()(intervals_4);
for(interval<int> i : intervals_4) std::cout << " {" << i.start() << ", " << i.end() << "}";
return 0;
}