找到多个间隔之间的最大差距

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (16)

想象一下,你有一个变量$ n表示时间轴上的多个分区,以及一个可变长度的间隔数组:

$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10],
];

问题是在时间线上找到这些间隔之间的最大差距。对于上面的问题,我们有两个长度为2和1的间隙,所以答案应该是2.为了更好地可视化:

我的直接方法效率不高......

  1. 初始化一个长度为$ n的空时间轴数组,每个元素设置为'E',如空。
  2. Foreach遍历每个间隔并从间隔开始到间隔结束创建另一个for循环,并将时间线数组中的这些元素设置为“T”,如同所采用的那样。
  3. 循环遍历时间轴数组并启动$计数器,该计数器随每个连续的'E'字符递增,如果它大于前一个,则将其值保存到变量$ max。

我可以做些什么改进?

请注意:

  • 间隔始终根据其起始位置进行排序。
  • 间隔不必从时间线的开头开始,也不必在时间线的末尾结束。因此,在第一个间隔之前可能存在间隙,在最后一个间隔之后可能存在间隙。
  • 间隔可以重叠。因此,简单地计算下一个区间的开始减去这个区间的结束将不起作用......考虑这个例子:[1,5] [2,4] [6,10] [6,8]
提问于
用户回答回答于

更新的解决方案:

$intervals = [
    [1,2],
    [2,2],
    [5,6],
    [8,10]
];
$rr = [];
foreach($intervals as $v){
    $rr[] = range($v[0],$v[1]);
}
$n = 10;
$range      = range(1,$n);
$diff =     array_diff($range,array_values(array_unique(array_merge(...$rr))));
$r = groupConsecutive($diff);

echo '<pre>';
print_r($r);

function  groupConsecutive($array) {
   $ret  = array();
   $temp = array();
   foreach($array as $val) {
      if(next($array) == ($val + 1))
         $temp[] = $val;
      else
         if(count($temp) > 0) {
            $temp[] = $val;
            $ret[]  = $temp;
            $temp   = array();
         }
         else
            $ret[] = $val;
   }
   return $ret;
}

DEMO

用户回答回答于

如果分区已排序(如您的示例中所示)。您可以迭代分区并创建一个包含以下内容的新数组:

  • 第一个数组中间隔的原始位置
  • 分区的第一个元素与前一个分区的最后一个元素的距离。

有了它,您将有一个分区之间的间隙列表。然后你只需对那些差距进行排序并选择最后一个。

但正如我所说,这是假设你的分区已经排序

有一个例子然后你$gaps按值的第二个元素排序并取最后一个。

<?php                                                                                                                                                                                                                                                         

$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10],
];

$gaps = array();

$prev_range_max = 1;
for ($i = 0; $i < count($intervals); $i++) {
    $gaps[] = Array($i, $intervals[$i][0] - $prev_range_max);
    $prev_range_max = $intervals[$i][1];
}

扫码关注云+社区

领取腾讯云代金券