JavaScript: Subtracting ranges of numbers

Question

I'm trying to write a JS function which has two parameters, include and exclude, each an array of objects {X, Y} which represents a range of numbers from X to Y, both included.

The output is the subtraction of all the ranges in include with all the ranges in exclude.

For example:

include = [ {1,7}, {9,10}, {12,14} ]
exclude = [ {4,5}, {11,20} ]
output  = [ {1,3}, {6,7}, {9,10} ]

• {4,5} broke {1,7} into two range objects: {1,3} and {6,7}
• {9,10} was not affected
• {12,14} was removed entirely

Answer 1

You can use sweep line algorithm. For every number save what it represents (start and end, inclusion and exclusion ). Then put all the number in an array and sort it. Then iteratively remove elements from the array and perform the appropriate operation.

include_list = [[1,7]]
exclude_list = [[4,5]]
(1,start,inclusion),(4,start,exclusion),(5,end,exclusion),(7,end,inclusion)

include = 0
exclude = 0
cur_element = (1,start,inclusion) -> include = 1, has_open_range = 1, range_start = 1 // we start a new range starting at 1
cur_element = (4,start,exclusion) -> exclude = 1, has_open_range = 0, result.append ( [1,4] ) // we close the open range and add range to result
cur_element = (5,end,exclusion) -> exclude = 0, has_open_range = 1, range_start = 5 // because include was 1 and exclude become 0 we must create a new range starting at 5
cur_element = (7,end,inclusion) -> include = 0, has_open_range = 0, result.append([5,7]) // include became zero so we must close the current open range so we add [5,7] to result

maintain variables include and exclude increment them with start of the respective elements and decrement them upon receiving end elements. According to the value of include and exclude you can determine wether you should start a new range, close the open range, or do nothing at all.

This algorithm runs in linear time O(n).