codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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; }
Private
[
?
]
Run code
Submit