Draft:Klee's algorithm

1. Separate the endpoint pairs for each interval and tag if each endpoint was on the left or the right.
2. Sort the individual endpoints in ascending order of value, with the additional condition that left endpoints are before right endpoints when two endpoint values are the same. (This changes any partially overlapping intervals into a series of nested ones.)
3. Iterate through the sorted endpoints, keeping track of the interval nesting count and recording just the outermost interval of each nesting.
4. Add up the measures of each of the resulting set of disjointed intervals.

The original pseudocode had the following lines inside of the loop through the endpoints:

${\displaystyle EXCESS=EXCESS+t_{i}}$ if ${\displaystyle EXCESS=1}$  then ${\displaystyle m=m+1}$  and ${\displaystyle c_{m}=e_{i}}$ if ${\displaystyle EXCESS=0}$  then ${\displaystyle d_{m}=e_{i}}$ 

where ${\displaystyle EXCESS}$ is the interval nesting count, ${\displaystyle i}$ is the current endpoint index, ${\displaystyle t_{i}}$ = +1 for left endpoints and -1 for right endpoints, ${\displaystyle e_{i}}$ is the current endpoint value, ${\displaystyle m}$ is the index of the current interval for the new set, and ${\displaystyle c_{m}}$ and ${\displaystyle d_{m}}$ are the start and end of the current interval for the new set, respectively. This code incorrectly jumps ahead ${\displaystyle m}$ at the right endpoint of the second outermost interval and uses that endpoint as the left endpoint of the next recorded interval.

To fix this problem, the pseudocode could be rewritten as follows:

if ${\displaystyle EXCESS=0}$  then ${\displaystyle m=m+1}$  and ${\displaystyle c_{m}=e_{i}}$ ${\displaystyle EXCESS=EXCESS+t_{i}}$ if ${\displaystyle EXCESS=0}$  then ${\displaystyle d_{m}=e_{i}}$ 

This way, the first line only triggers before the first endpoint of a nested set of endpoints and the second line only triggers after the end of the last endpoint of such a set.

function measureOfUnion(intervals = []) {    // the input is expected to be an array of intervals,    // with each interval being a 2-element array    const endpoints = [];    for (let interval of intervals) {        endpoints.push({v: interval[0], nestingChange: +1});        endpoints.push({v: interval[1], nestingChange: -1});    }    endpoints.sort(endpointSort);    const disjointIntervals = [];    let nestingLevel = 0;    let currentInterval;    for (let endpoint of endpoints) {        if (nestingLevel === 0) {            currentInterval = [endpoint.v];            disjointIntervals.push(currentInterval);        }        nestingLevel += endpoint.nestingChange;        if (nestingLevel === 0)            currentInterval.push(endpoint.v);    }    let measure = 0;    for (let interval of disjointIntervals) {        measure += interval[1] - interval[0];    }    return measure;}function endpointSort(a, b) {    // normal expression for ascending order    if (a.v != b.v) return a.v - b.v;    // swap endpoints if the first one ends an interval    if (a.nestingChange == -1) return +1;    // otherwise, stay in this order    return -1;}