JavaScript:减去数字范围

Question

我正在尝试编写一个JS函数,它有两个参数,include和exclude,每个参数都是一个对象{X,Y}的数组,表示从X到Y的数字范围,两者都包括在内.

输出是包含所有范围的所有范围的减法,其中包括排除中的所有范围.

例如:

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

• {4,5}将{1,7}分成两个范围对象:{1,3}和{6,7}
• {9,10}没有受到影响
• {12,14}完全被删除

Answer 1

您可以使用扫线算法。对于每个数字，保存它所代表的内容（开始和结束、包含和排除）。然后将所有数字放入一个数组中并排序。然后迭代地从数组中删除元素并执行适当的操作。

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

维护变量include并exclude在相应元素的开始时递增它们，并在接收结束元素时递减它们。include根据和的值，exclude您可以确定是应该开始一个新的范围、关闭打开的范围还是什么都不做。

该算法的运行时间为线性时间 O(n)。