1.
Introduction
2.
Examples of Klee's Algorithm
Last Updated: Mar 27, 2024

# Klee’s Algorithm

0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## 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.

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;

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp
Live masterclass