// C++ program to implement Klee's algorithm   #include       using     namespace     std  ;   // Returns sum of lengths covered by union of given   // segments   int     segmentUnionLength  (  const     vector   <         pair      <  int    int  >     >     &  seg  )   {      int     n     =     seg  .  size  ();      // Create a vector to store starting and ending      // points      vector      <  pair      <  int       bool  >     >     points  (  n     *     2  );      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      {      points  [  i  *  2  ]     =     make_pair  (  seg  [  i  ].  first       false  );      points  [  i  *  2     +     1  ]     =     make_pair  (  seg  [  i  ].  second       true  );      }      // Sorting all points by point value      sort  (  points  .  begin  ()     points  .  end  ());      int     result     =     0  ;     // Initialize result      // To keep track of counts of       // current open segments      // (Starting point is processed       // but ending point      // is not)      int     Counter     =     0  ;      // Traverse through all points      for     (  unsigned     i  =  0  ;     i   <  n  *  2  ;     i  ++  )      {      // If there are open points then we add the      // difference between previous and current point.      // This is interesting as we don't check whether      // current point is opening or closing      if     (  Counter  )      result     +=     (  points  [  i  ].  first     -         points  [  i  -1  ].  first  );      // If this is an ending point reduce count of      // open points.      (  points  [  i  ].  second  )  ?     Counter  --     :     Counter  ++  ;      }      return     result  ;   }   // Driver program for the above code   int     main  ()   {      vector   <     pair      <  int    int  >     >     segments  ;      segments  .  push_back  (  make_pair  (  2       5  ));      segments  .  push_back  (  make_pair  (  4       8  ));      segments  .  push_back  (  make_pair  (  9       12  ));      cout      < <     segmentUnionLength  (  segments  )      < <     endl  ;      return     0  ;   }   

   // Java program to implement Klee's algorithm   import     java.io.*  ;   import     java.util.*  ;   class   GFG     {      // to use create a pair of segments      static     class   SegmentPair      {      int     x    y  ;      SegmentPair  (  int     xx       int     yy  ){      this  .  x     =     xx  ;      this  .  y     =     yy  ;      }      }      //to create a pair of points      static     class   PointPair  {      int     x  ;      boolean     isEnding  ;      PointPair  (  int     xx       boolean     end  ){      this  .  x     =     xx  ;      this  .  isEnding     =     end  ;      }      }      // creates the comparator for comparing objects of PointPair class      static     class   Comp     implements     Comparator   <  PointPair  >      {          // override the compare() method      public     int     compare  (  PointPair     p1       PointPair     p2  )      {      if     (  p1  .  x      <     p2  .  x  )     {      return     -  1  ;      }      else     {      if  (  p1  .  x     ==     p2  .  x  ){      return     0  ;      }  else  {      return     1  ;      }      }      }      }      public     static     int     segmentUnionLength  (  List   <  SegmentPair  >     segments  ){      int     n     =     segments  .  size  ();      // Create a list to store       // starting and ending points      List   <  PointPair  >     points     =     new     ArrayList   <>  ();      for  (  int     i     =     0  ;     i      <     n  ;     i  ++  ){      points  .  add  (  new     PointPair  (  segments  .  get  (  i  ).  x    false  ));      points  .  add  (  new     PointPair  (  segments  .  get  (  i  ).  y    true  ));      }          // Sorting all points by point value      Collections  .  sort  (  points       new     Comp  ());      int     result     =     0  ;     // Initialize result      // To keep track of counts of      // current open segments      // (Starting point is processed      // but ending point      // is not)      int     Counter     =     0  ;      // Traverse through all points      for  (  int     i     =     0  ;     i      <     2     *     n  ;     i  ++  )      {          // If there are open points then we add the      // difference between previous and current point.      // This is interesting as we don't check whether      // current point is opening or closing      if     (  Counter     !=     0  )      {      result     +=     (  points  .  get  (  i  ).  x     -     points  .  get  (  i  -  1  ).  x  );      }      // If this is an ending point reduce count of      // open points.      if  (  points  .  get  (  i  ).  isEnding  )      {      Counter  --  ;      }      else      {      Counter  ++  ;      }      }      return     result  ;      }      // Driver Code      public     static     void     main     (  String  []     args  )     {      List   <  SegmentPair  >     segments     =     new     ArrayList   <>  ();      segments  .  add  (  new     SegmentPair  (  2    5  ));      segments  .  add  (  new     SegmentPair  (  4    8  ));      segments  .  add  (  new     SegmentPair  (  9    12  ));      System  .  out  .  println  (  segmentUnionLength  (  segments  ));      }   }   // This code is contributed by shruti456rawal   

   # Python program for the above approach   def   segmentUnionLength  (  segments  ):   # Size of given segments list   n   =   len  (  segments  )   # Initialize empty points container   points   =   [  None  ]   *   (  n   *   2  )   # Create a vector to store starting    # and ending points   for   i   in   range  (  n  ):   points  [  i   *   2  ]   =   (  segments  [  i  ][  0  ]   False  )   points  [  i   *   2   +   1  ]   =   (  segments  [  i  ][  1  ]   True  )   # Sorting all points by point value   points   =   sorted  (  points     key  =  lambda   x  :   x  [  0  ])   # Initialize result as 0   result   =   0   # To keep track of counts of current open segments   # (Starting point is processed but ending point   # is not)   Counter   =   0   # Traverse through all points   for   i   in   range  (  0     n   *   2  ):   # If there are open points then we add the   # difference between previous and current point.   if   (  i   >   0  )   &   (  points  [  i  ][  0  ]   >   points  [  i   -   1  ][  0  ])   &   (  Counter   >   0  ):   result   +=   (  points  [  i  ][  0  ]   -   points  [  i   -   1  ][  0  ])   # If this is an ending point reduce count of   # open points.   if   points  [  i  ][  1  ]:   Counter   -=   1   else  :   Counter   +=   1   return   result   # Driver code   if   __name__   ==   '__main__'  :   segments   =   [(  2     5  )   (  4     8  )   (  9     12  )]   print  (  segmentUnionLength  (  segments  ))   

   using     System  ;   using     System.Collections  ;   using     System.Collections.Generic  ;   using     System.Linq  ;   // C# program to implement Klee's algorithm   class     HelloWorld     {      class     GFG     :     IComparer   <  KeyValuePair   <  int       bool  >>      {      public     int     Compare  (  KeyValuePair   <  int       bool  >     x    KeyValuePair   <  int       bool  >     y  )      {      // CompareTo() method      return     x  .  Key  .  CompareTo  (  y  .  Key  );      }      }      // Returns sum of lengths covered by union of given      // segments      public     static     int     segmentUnionLength  (  List   <  KeyValuePair   <  int    int  >>     seg  )      {      int     n     =     seg  .  Count  ;      // Create a vector to store starting and ending      // points      List   <  KeyValuePair   <  int       bool  >>     points     =     new     List   <  KeyValuePair   <  int       bool  >>  ();      for  (  int     i     =     0  ;     i      <     2  *  n  ;     i  ++  ){      points  .  Add  (  new     KeyValuePair   <  int       bool  >     (  0    true  ));      }         for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      {      points  [  i  *  2  ]     =     new     KeyValuePair   <  int       bool  >     (  seg  [  i  ].  Key       false  );      points  [  i  *  2     +     1  ]     =     new     KeyValuePair   <  int       bool  >     (  seg  [  i  ].  Value       true  );      }      // Sorting all points by point value      GFG     gg     =     new     GFG  ();      points  .  Sort  (  gg  );      int     result     =     0  ;     // Initialize result      // To keep track of counts of       // current open segments      // (Starting point is processed       // but ending point      // is not)      int     Counter     =     0  ;      // Traverse through all points      for     (  int     i  =  0  ;     i   <  n  *  2  ;     i  ++  )      {      // If there are open points then we add the      // difference between previous and current point.      // This is interesting as we don't check whether      // current point is opening or closing      if     (  Counter     !=     0  )      result     +=     (  points  [  i  ].  Key     -     points  [  i  -  1  ].  Key  );      // If this is an ending point reduce count of      // open points.      if  (  points  [  i  ].  Value     !=     false  ){      Counter  --  ;      }      else  {      Counter  ++  ;      }      }      return     result  ;      }      static     void     Main  ()     {      List   <  KeyValuePair   <  int    int  >>     segments     =     new     List   <  KeyValuePair   <  int    int  >>     ();      segments  .  Add  (  new     KeyValuePair   <  int    int  >     (  2       5  ));      segments  .  Add  (  new     KeyValuePair   <  int    int  >     (  4       8  ));      segments  .  Add  (  new     KeyValuePair   <  int    int  >     (  9       12  ));      Console  .  WriteLine  (  segmentUnionLength  (  segments  ));      }   }   // The code is contributed by Nidhi goel.    

   // JavaScript program to implement Klee's algorithm   // Returns sum of lengths covered by union of given   // segments   function     segmentUnionLength  (  seg  )   {      let     n     =     seg  .  length  ;      // Create a vector to store starting and ending      // points      let     points     =     new     Array  (  2  *  n  );      for     (  let     i     =     0  ;     i      <     n  ;     i  ++  )      {      points  [  i  *  2  ]     =     [  seg  [  i  ][  0  ]     false  ];      points  [  i  *  2     +     1  ]     =     [  seg  [  i  ][  1  ]     true  ];      }      // Sorting all points by point value      points  .  sort  (  function  (  a       b  ){      return     a  [  0  ]     -     b  [  0  ];      });          let     result     =     0  ;     // Initialize result      // To keep track of counts of       // current open segments      // (Starting point is processed       // but ending point      // is not)      let     Counter     =     0  ;      // Traverse through all points      for     (  let     i  =  0  ;     i   <  n  *  2  ;     i  ++  )      {      // If there are open points then we add the      // difference between previous and current point.      // This is interesting as we don't check whether      // current point is opening or closing      if     (  Counter  )      result     +=     (  points  [  i  ][  0  ]     -     points  [  i  -  1  ][  0  ]);      // If this is an ending point reduce count of      // open points.      if  (  points  [  i  ][  1  ]){      Counter     =     Counter     -     1  ;      }      else  {      Counter     =     Counter     +     1  ;      }      }      return     result  ;   }   let     segments     =     new     Array  ();   segments  .  push  ([  2       5  ]);   segments  .  push  ([  4       8  ]);   segments  .  push  ([  9       12  ]);   console  .  log  (  segmentUnionLength  (  segments  ));   // The code is contributed by Gautam goel (gautamgoel962)