Implementation of Klee’s Algorithm in C++

In this tutorial, we are going to see the Implementation of Klee’s Algorithm in C++. Here we will learn about Klee’s algorithm, how it works, and after that, we will see the C++ program for the same.

Given a set of line segments with the starting and ending point in the form of pairs. We have to find the maximum continuous length after taking the union of all the pairs of line segments.

kees algorithm

For example:-

arr={{1,6},{4,5},{3,8},{7,9}}

Output: 8

arr={{1,3},{2,5},{5,6}}

Output: 5

Klee’s Algorithm

Klee’s Algorithm is introduced by a mathematician Victor Klee¬†in 1977. The time complexity of the algorithm is O (n log n). This algorithm uses sorting that’s why it has a time complexity of O(nlogn). Let us see the algorithm.

Algorithm

1. Create a vector of pairs where each pair contain a value of starting/ending point and false if it is a starting point or true if it is an ending point eg. for {2,3}—>{{2,false},{3,true}}.
2. Sort the vector in ascending order using in-built function sort(). And if in case two values are equal, then starting point value will have more priority and comes first in order.
3. Now, traverse the whole vector using for loop.
4. We take two variables ‘answer’ and ‘counter’, ‘answer’ stores the result and if the counter is non-zero, we will add the difference of the points to the result.
5.¬† And ‘counter’ will be incremented by 1 if the point is a starting point (contain false) and decremented by 1 if the point is an ending point (contain true).
6. Display the output.

C++ implementation of Klee’s Algorithm

So, here is the C++ implementation of the above algorithm:-

#include<bits/stdc++.h> 
using namespace std; 



/*=========================================================
    FUNCTION TO FIND THE LENGTH AFTER TAKING UNION OF ALL
==========================================================*/
int find_union(vector<pair<int,int>> vect) 
{ 
  int size = vect.size(); 

  // Create a vector to store starting and ending 
  // points separately and if it is starting insert false in
  //pair and if it is ending point insert true in pair.
  vector <pair <int, bool> > endpoints(size * 2); 
  for (int i = 0; i < size; i++) 
  { 
    endpoints[i*2]  = make_pair(vect[i].first, false); 
    endpoints[i*2 + 1] = make_pair(vect[i].second, true); 
  } 

  // Sorting all endpoints
  sort(endpoints.begin(), endpoints.end()); 

  //Initialising two variables
  //answer stores the final length
  //counter keep tracks of opening & closing of segments
  int answer = 0; 
  int counter = 0; 

  // Traverse through all endpoints 
  for (int i=0; i<size*2; i++) 
  { 
    // If the counter is non-zero then we add the 
    //difference of curr and prev points to answer 
    if (counter) 
      answer+=(endpoints[i].first - endpoints[i-1].first); 

    // If endpoint is ending point of segment decrement
    // the counter else increment the counter
    if (endpoints[i].second)
      counter--;
    else
      counter++; 
  } 
  return answer; 
} 

/*======================================
             MAIN FUNCTION
=======================================*/
int main() 
{ 
  //Initialising vector of pairs
  vector< pair <int,int> > vect; 

  //Inserting endpoints of line segments
  vect.push_back(make_pair(1, 6)); 
  vect.push_back(make_pair(4, 5)); 
  vect.push_back(make_pair(3, 8)); 
  vect.push_back(make_pair(7, 9)); 

  //Calling find_union() function
  int ans=find_union(vect);

  //Displaying output
  cout<<"Final length after taking union of all segments = " 
      <<ans<<endl; 
  return 0; 
} 

Output:-

Final length after taking union of all segments = 8

Time Complexity:- O(n*logn)

Thanks for reading this tutorial. I hope it helps you !!

Leave a Reply