如果我有一个现有范围:
1-10
11-50
然后我将输入一个新的范围从1 - 60,我如何检测要添加的新范围与之前的条目重叠?我怎样才能得到可用的范围呢?在本例中,可用范围为51-60。
这里有人有什么好主意吗?谢谢你的帮助。
下面是我当前的代码:
$saved = array(
array(
"start" => 1,
"end" => 10
),
array(
"start" => 10,
"end" => 50
)
);
$new_range = array(
"start" => 1,
"end" => 60
);
$usable_range = array();
$previous_from = 0;
$previous_to = 0;
foreach($saved as $value)
{
$range_start = 0;
$range_end = 0;
if($previous_from<$value['start'])
{
$previous_from = $value['start'];
}
if($previous_to<$value['end'])
{
$previous_to = $value['end'];
}
if($previous_from<=$new_range['start'])
{
if($previous_to<$new_range['end'])
{
$range_start = $previous_to+1;
$range_end = $new_range['end'];
$new_range['start'] = $range_start;
}
}
else if($previous_from>=$new_range['start'])
{
if($previous_to<$new_range['end'])
{
$range_start = $previous_to+1;
$range_end = $new_range['end'];
$new_range['start'] = $range_start;
}
}
$usable[] = array("range_start"=>$range_start,"range_end"=>$range_end);
}
Call every interval (min,max)
1)按min
对间隔列表进行排序。
2)检查max
是否大于min
上的下一个条目。如果是,则创建最小值较小、最大值较大的间隔,并将其添加回列表中,以取代这两个值。
3)每当你得到一个新的区间,二分搜索到列表中添加它,按min
排序。然后,使用与2)中类似的逻辑,尝试将其与条目(上下各一个)合并,直到不能再合并为止。
编辑:一些改动。
首先,因为我们使用的是整数而不是浮点数,如果你有一个区间,比如1,10和11,20,那么在10和11之间没有"间隙"——所以我们应该把它看作一个更大的区间,1,20。反映这一点,而不是检查max > next min
,如果max >= next min - 1
.
第二,如果你想在合并一个新区间到你的区间列表时找到所有由重叠形成的区间:
1)由于已知区间列表处于由min
排序并由max
排序的状态,因此对其进行二进制搜索以找到刚好高于新最小值的最低最小值和刚好高于新最大值的最高最大值。
2)遍历min, max, min, max…等等,在新的最小值和新的最大值之间。低于最低最小值,高于最高最大值,以及在每个最大值/最小值之间,您可以计算在"间隙"中的间隔,并以例如数组的形式返回它们。
例如,如果你的区间列表包含13,16,21,24和31,38,并且你想计算新区间1,30的非重叠:
1)我们对列表进行二分搜索,发现13是大于1的最小值,24是大于30的最大值。
- 我们的最小值和最小值之间是1和13 -所以这形成了一个区间1,12(包括底部,不包括顶部)。添加到返回数组。
- 在最大值和下一个最小值之间是16和21 -所以这形成了一个间隔17,20(不包括两端)。添加到返回数组。
- max和我们的max之间是24和30 -所以这形成了一个间隔25,30(不包括底部,包括顶部)。添加到返回数组。
找到重叠可以被描述为找到一个交集。同样,找到可用范围也可以被描述为找到差值。一种方法是将这些集合视为数组,并使用array_intersect[1]和array_diff[2]函数。
鉴于你的详细情况,我只能想出这么多了。
[1] - http://php.net/manual/en/function.array-intersect.php
[2]——http://www.php.net/manual/en/function.array-diff.php