1

如果我有一个现有范围：

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);             
            }
4

2 回答 2

1

调用每个间隔（最小，最大）

1) 按它们对间隔列表进行排序min。

2) 检查是否有任何max大于下一个条目 over's min。如果是，则创建最小值和最大值中较大的间隔，并将其添加回列表中以代替这两个。

3）每当你得到一个新的区间，二进制搜索到列表中添加它，按min. 然后，使用与 2) 中类似的逻辑，尝试将其与下面的条目 1 和上面的条目合并，直到无法再合并。

编辑：一些变化。

首先，因为我们使用的是整数而不是浮点数，如果你有一个像 1,10 和 11,20 这样的区间，那么 10 和 11 之间就没有“间隙”——所以我们应该认为这是一个更大的区间，1， 20. 反映这一点，而不是检查 if max > next min， if max >= next min - 1。

其次，如果您想在将新间隔合并到间隔列表中时找到由重叠形成的所有间隔：

1) 由于已知间隔列表处于按 排序min和排序的状态，因此对它进行max二进制搜索以找到刚好高于新最小值的最低最小值和刚好高于新最大值的最高最大值。

2) 遍历数组中的最小值、最大值、最小值、最大值……等，这些值介于新最小值和新最大值之间。低于最低最小值，高于最高最大值以及在每个最大值/最小值之间，您可以计算“间隙”中的间隔，并将它们返回到例如数组中。

例如，如果您的区间列表包含 13,16, 21,24 和 31, 38，并且您想要计算新区间 1,30 的非重叠：

1）我们对我们的列表进行二分搜索，发现 13 是高于 1 的最低最小值，而 24 是高于 30 的最高最大值。

2）我们这样迭代：

  • 在我们的最小值和最低最小值之间是 1 和 13 - 所以这形成了一个区间 1,12（包括底部，不包括顶部）。添加到返回数组。
  • 最大值和下一个最小值之间是 16 和 21 - 所以这形成了一个间隔 17,20（不包括两端）。添加到返回数组。
  • 在 max 和我们的 max 之间是 24 和 30 - 所以这形成了一个区间 25,30（不包括底部，包括顶部）。添加到返回数组。
于 2013-05-09T03:34:03.007 回答
-1

寻找重叠可以描述为寻找交叉点。同样找到可用范围可以描述为找到差异。一种方法是将这些集合视为数组并使用 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

于 2013-05-09T03:35:02.483 回答