首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >查找多个间隔之间的最长间隔

查找多个间隔之间的最长间隔
EN

Stack Overflow用户
提问于 2019-06-23 18:24:27
回答 5查看 1.3K关注 0票数 5

假设您有一个变量$n,表示时间轴上的多个分区,以及一个可变长度的间隔数组:

代码语言:javascript
复制
$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10],
];

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

我的直截了当的方法效率不高。

  1. 初始化一个长度为$n的空时间线数组,每个元素都设置为'E‘,就像在empty中一样。
  2. 在每个时间间隔内循环,并创建另一个从间隔开始到时间间隔结束的for循环,并将时间线数组中的这些元素设置为'T’,就像在taken中一样。
  3. 循环时间线数组,并启动一个每个连续的'E‘字符递增的$counter,然后如果它的值大于前一个,则将其值保存到变量$max中。

我可以做哪些改进?

请注意:

时间间隔总是根据它们的开始进行排序的,positions.

  • Intervals不一定要从时间轴的开头开始,也不一定要在时间轴的末尾结束。因此,在第一个间隔之前可能存在间隙,而在最后一个interval.

  • Intervals之后可能存在间隙。因此,简单地计算下一个间隔的开始减去这个间隔的结束是行不通的…考虑这个例子: 1,5,6,10
EN

回答 5

Stack Overflow用户

回答已采纳

发布于 2019-06-23 22:07:16

代码语言:javascript
复制
<?php

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

$non_overlapping = [];
$start = -1;
$end = -1;

foreach($intervals as $index => $interval){
    if($start == -1) $start = $interval[0];
    if($end == -1) $end = $interval[1];

    if($index == 0) continue; // since it's first index

    if($interval[0] >= $end){
        $non_overlapping[] = [$start,$end];
        $start = $interval[0];
        $end = $interval[1];
    }else{
        $end = max($end,$interval[1]);
    }
}

$non_overlapping[] = [$start,$end];
$maximum_gap = 0;
$prev_end = 0;

foreach($non_overlapping as $index => $interval){
    $maximum_gap = max($maximum_gap,$interval[0] - $prev_end - 1);
    $prev_end = $interval[1];
}

$maximum_gap = max($maximum_gap,$n - $prev_end);

echo $maximum_gap;

  • 由于您的间隔是根据开始时间进行排序的,因此我们创建了一个新的非重叠间隔数组。
  • 现在,我们只需要用以前的结束时间减去新的开始时间,最后用$n本身减去最后的结束时间,就可以找到最大的差距。
票数 1
EN

Stack Overflow用户

发布于 2019-06-23 19:01:42

更新的解决方案:-

代码语言:javascript
复制
$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);

$max = 0;
if (count($r)) {
    foreach ($r as $gap) {
        $length = 1;
        if (is_array($gap)) $length = count($gap);
        if ($max < $length) $max = $length;
    }
}

echo $max;

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

票数 1
EN

Stack Overflow用户

发布于 2019-06-23 19:04:03

是否对分区进行了排序(如示例中所示)。您可以遍历分区并创建一个包含以下内容的新数组:

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

这样你就有了一个分区之间的空隙列表。然后,您只需对这些空格进行排序,并采用最后一个空格。

但正如我已经说过的,这是假设您的分区是排序的。

这里有一个示例,然后按值的第二个元素对$gaps进行排序,并取最后一个元素。

代码语言:javascript
复制
<?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];
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56722946

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档