My math-fu is failing me! I need an efficient way of reducing network ranges to supersets, e.g. if I input list of IP ranges:

- 1.1.1.1 to 2.2.2.5
- 1.1.1.2 to 2.2.2.4
- 10.5.5.5 to 155.5.5.5
- 10.5.5.6 to 10.5.5.7

I want to return the following ranges:

- 1.1.1.1 to 2.2.2.5
- 10.5.5.5 to 155.5.5.5

Note: the input lists are not ordered (though they could be?). The naive way to do this is to check every range in the list to see if the input range x is a subset, and if so, NOT insert range x. However, whenever you insert a new range it might be a superset of existing ranges, so you have to check the existing ranges to see if they can be collapsed (e.g., removed from my list).

## Best Solution

This is a union of segments computation. An optimal algorithm (in O(nlog(n))) consists in doing the following:

LE-RE, whereLEis the number of left endpoints that you have already passed, andREis the number of right endpoints that you have already passed.LE-REreaches zero, you are at the end of a connected union of segments, and you know that the union of the segments you have seen before (since the previous return to zero) is one superset.At the end, you obtain a sorted list of disjoint supersets. Still, two supersets A and B can be adjacent (the endpoint of A is just before the starting point of B). If you want A and B to be merged, you can do this either by a simple postprocessing step, or by slightly modifying step 3: when

LE-REreaches zero, you would consider it the end of a superset only if the next element in L is not the direct successor of your current element.