need an algorithm for collapsing netblock ranges into lists of superset ranges

by

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

  1. sort all endpoints (starting and ending points) in a list L (each endpoint should know the segment it belongs to). If an endpoint is equal to a starting point, the starting point should be considered smaller than the enpoint.
  2. go through the sorted list L from left to right and maintain the number LE-RE, where LE is the number of left endpoints that you have already passed, and RE is the number of right endpoints that you have already passed.
  3. each time LE-RE reaches 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.
  4. if you also maintained the min and max, between each return to zero, you have the bounds of the 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-RE reaches 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.

More Related Contents:

  1. Algorithm to find Largest prime factor of a number
  2. Write a function that returns the longest palindrome in a given string
  3. Cycles in an Undirected Graph
  4. Efficiently find binary strings with low Hamming distance in large set
  5. Roulette wheel selection algorithm [duplicate]
  6. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  7. Calculating mid in binary search
  8. Geo Fencing – point inside/outside polygon
  9. Find the missing and duplicate elements in an array in linear time and constant space
  10. Best Compression algorithm for a sequence of integers
  11. Smoothing data from a sensor
  12. A simple explanation of Naive Bayes Classification [closed]
  13. Basic Recursion, Check Balanced Parenthesis
  14. Euler project #18 approach
  15. Fastest available algorithm for distance transform
  16. What algorithm for a tic-tac-toe game can I use to determine the “best move” for the AI?
  17. Generating integers in ascending order using a set of prime numbers
  18. Big O when adding together different routines
  19. Finding height in Binary Search Tree
  20. How to understand the dynamic programming solution in linear partitioning?
  21. Clustering Algorithm for Mapping Application
  22. Algorithm for permutations of operators and operands
  23. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  24. How do I find the median of numbers in linear time using heaps?
  25. Optimized low-accuracy approximation to `rootn(x, n)`
  26. What are probabilistic data structures?
  27. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  28. Finding rectangles in a 2d block grid
  29. Connected Component Labeling – Implementation
  30. Algorithm to list all unique permutations of numbers contain duplicates

Leave a Comment