// 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 <intint> > &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 <intint> > 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 xy;  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).xfalse));  points.add(new PointPair(segments.get(i).ytrue));  }    // 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(25));  segments.add(new SegmentPair(48));  segments.add(new SegmentPair(912));  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> xKeyValuePair<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<intint>> 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> (0true));  }   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<intint>> segments = new List<KeyValuePair<intint>> ();  segments.Add(new KeyValuePair<intint> (2 5));  segments.Add(new KeyValuePair<intint> (4 8));  segments.Add(new KeyValuePair<intint> (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)