pmcgee

Collapse Intervals

May 9th, 2021
822
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <numeric>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <list>
  6. #include <iostream>
  7. using namespace std;
  8.  
  9. using   itvl = std::pair< int, int >;
  10. using  Litvl = std::list< itvl >;
  11.  
  12. vector< itvl >    intervalz  {  {1,2},   {1,5},   {2,3},   {6,8},
  13.                                 {7,10},  {8,11},  {14,18}, {99,99}
  14.                              };
  15.  
  16. struct  Acc {
  17.          itvl  current;  // {0,0};
  18.         Litvl  list   ;  // {};
  19. } acc;
  20.  
  21.  
  22. auto consume = []  ( Acc& acc, const itvl& i)                          // assumes sorted on interval first element
  23.                        {
  24.                           if ( i.first > acc.current.second ) {        // disjoint intervals
  25.                                  acc.list.push_back( acc.current );
  26.                                  acc.current = i;
  27.                           }
  28.                           else                                         // overlap
  29.                           if ( i.second > acc.current.second ) {
  30.                                  acc.current.second = i.second;        // -> extend
  31.                           }
  32.                           else
  33.                              ;                                         // -> swallow
  34.                           return acc;
  35.                        };
  36.  
  37.  
  38. int main()
  39. {
  40.     auto d  = accumulate ( intervalz.begin(),
  41.                            intervalz.end(),
  42.                            acc,
  43.                            consume);
  44.  
  45.     cout <<  d.current.first << " " << d.current.second << "\n\n";
  46.  
  47.     for ( auto i : d.list)  {
  48.           cout <<  i.first << " " << i.second << "\n";
  49.     }
  50.  
  51.     getchar();
  52.     return 0;
  53. }
RAW Paste Data