## Monday, October 10, 2016

### Klee's Algorithm (Length Of Union Of Segments of a line) - GeeksforGeeks

Klee's Algorithm (Length Of Union Of Segments of a line) - GeeksforGeeks
Given starting and ending positions of segments on a line, the task is to take the union of all given segments and find length covered by these segments.

```Input : segments[] = {{2, 5}, {4, 8}, {9, 12}}
Output : 9
segment 1 = {2, 5}
segment 2 = {4, 8}
segment 3 = {9, 12}
If we take the union of all the line segments,
we cover distances [2, 8] and [9, 12]. Sum of
these two distances is 9 (6 + 3)
```

The algorithm was proposed by Klee in 1977. The time complexity of the algorithm is O (N log N). It has been proven that this algorithm is the fastest (asymptotically) and this problem can not be solved with a better complexity.

`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;`

`    ``// Trvaerse 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;`
`}`