Klee’s Algorithm

Introduction

Klee’s rule finds a union of line segments lying horizontally. OR total length lined by horizontal line segments once seen vertically. The rule was planned by Paul Klee in 1977.

The time complexity of the rule is O (N log N). It’s been verified that this rule is the quickest (asymptotically) and this drawback can’t be resolved with better quality.

Must Read, floyd's algorithm

Check This Out, binary search algorithm

Examples of Klee's Algorithm

Input: segments[] = {{2, 6}, {4, 7}, {9, 15}}
Output: 9
segment one = {2, 6}
segment two = {4, 7}
segment three = {9, 15}
If we have a tendency to take the union of all the line segments,
we will take distances [2, 7] and [9, 15]. Sum of
these 2 distances covered is 11 (5 + 6)

// Java program to implement Klee’s algorithm
class Solution {
public:
int findPoisonedDuration(vector& timeSeries, int duration) {
int n = timeSeries.size();
vector > inter;
int i=0;
for (; i < N; i++) {
int s = timeSeries[i];
int e = timeSeries[i] + duration;
inter.emplace_back(make_pair(s, false));
inter.emplace_back(make_pair(e, true));
}
sort(inter.begin(), inter.end());
assert((int) inter.size() == 2 * n);
int counter = 0;
int sum = 0;
i=0;
while(i<2*N){
if (counter) {
sum += inter[i].first – inter[i – 1].first;
}
if (inter[i].second) counter–;
else counter++;
i++;
}
return sum;
}
};

// C++ program to implement Klee’s algorithm

#include<bits/stdc++.h>

using namespace std;

// Returns total lengths covered by the union of given
// segments
int segmentUnionLength(const vector > &seg)
{
int n = seg.size();

// Create a vector for storing the start and end
// points 
vector <pair <int, bool> > points(n * 2); 
     int i=0;
for (; i < N; i++) 
{ 
    points[i*2]     = make_pair(seg[i].first, false); 
    points[i*2 + 1] = make_pair(seg[i].second, true); 
} 

// Sorting rhe all points by point value 
sort(points.begin(), points.end()); 

int result = 0; // Initialize result 

// To stay track of counts of current open segments 
// (Starting point is processed however 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 take sum of the 
    // difference between previous and current point. 
    // This can be fascinating as we don't check whether 
    // current point is opening or closing, 
    if (Counter) 
        result += (points[i].first - points[i-1].first); 

    // If this can be associate ending point, reduce, count of 
    // open points. 
    (points[i].second)? Counter-- : Counter++; 
} 
return result; 

}

// Driver program for the above code
int main()
{
vector< pair > segments;
segments.push_back(make_pair(3, 15));
segments.push_back(make_pair(2, 5));
segments.push_back(make_pair(4, 8));
segments.push_back(make_pair(9, 12));
cout << “Length of Union of All segments = “;
cout << segmentUnionLength(segments) << endl;
return 0;
}

Output:

Length/Distance of Union of All segments = 9

Description:

• Place all the coordinates of all the segments in associate auxiliary array points[].
• Sort it according to the value of the coordinates.
• An extra condition for sorting – if there are equal coordinates, insert the one which is the left coordinate of any segment instead of a right one.
• Now go through the entire array, with the counter “count” of overlapping segments.
• If count is greater than 0, then we add the result to the difference between the points[i] – points[i-1].
• If the current element belongs to the left end, we increase “count”, otherwise decrement it.

Illustration:

Lets take the example :
segment 1 : (2,5)
segment 2 : (4,8)
segment 3 : (9,12)

Counter = result = 0;
n = number of segments = 3;

for i=0, points[0] = {2, false}
points[1] = {5, true}
for i=1, points[2] = {4, false}
points[3] = {8, true}
for i=2, points[4] = {9, false}
points[5] = {12, true}

Therefore :
points = {2, 5, 4, 8, 9, 12}
{f, t, f, t, f, t}

after applying sorting :
points = {2, 4, 5, 8, 9, 12}
{f, f, t, t, f, t}

Now,
for i=0, result = 0;
Counter = 1;

for i=1, result = 2;
Counter = 2;

for i=2, result = 3;
Counter = 1;

for i=3, result = 6;
Counter = 0;

for i=4, result = 6;
Counter = 1;

for i=5, result = 9;
Counter = 0;

Final answer = 9;