如何获取指定全局数值区间内已占用范围间的未占用段数组
计算全局区间内的未占用数值范围
已知输入
现有一组记录了已被占用的数值范围的数组,每条数据对应一个独立分组的占用区间,包含分组ID、分组名称、区间起止值字段,原始数据结构如下:
[ {Id: '1', Title: 'Group A', Start: '100', End: '200'}, {Id: '2', Title: 'Group B', Start: '350', End: '500'}, {Id: '3', Title: 'Group C', Start: '600', End: '800'} ]
任务要求
基于100-999的全局固定覆盖区间,计算所有未被上述已占用范围覆盖的连续数值区间,最终输出仅包含Start、End字段的对象数组,预期输出结果为:
[ {Start: '201', End: '349'}, {Start: '501', End: '599'}, {Start: '801', End: '999'} ]
实际实现思路
写计算逻辑的时候要避开几个常见的计算错误点:
- 首先要对原始占用数组按
Start字段做升序排序,如果传入的数组顺序是乱的,直接按原顺序遍历一定会算出错误的结果 - 维护一个移动游标,初始化值设为全局区间的起点100
- 逐次遍历排序后的占用区间,对比当前游标和区间Start的大小:
- 如果游标值小于当前区间的Start值,说明两个位置之间存在连续的未占用间隙,将
[当前游标值, 当前区间Start值 - 1]记录为一个有效空闲区间 - 对比完成后将游标移动到“当前区间End值 + 1”的位置,继续处理下一个占用区间
- 如果游标值小于当前区间的Start值,说明两个位置之间存在连续的未占用间隙,将
- 遍历完所有占用区间后,需要检查剩余尾部范围:如果当前游标值仍小于全局区间的终点999,就将
[当前游标值, 999]作为最后一个空闲区间补入结果数组
内容的提问来源于stack exchange,提问作者Behnam
相关产品推荐
相关产品推荐

