找到多个间隔之间的最长间隔

Question

想象一下，您有一个变量 $n 表示时间线上的多个分区，以及一个可变长度的间隔数组：

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

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

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

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

我可以做哪些改进？

请注意：

• 间隔总是根据它们的开始位置进行排序。
• 间隔不必从时间线的开头开始，也不必在时间线的结尾处结束。因此，在第一个间隔之前可能有一个间隙，在最后一个间隔之后可能有一个间隙。
• 间隔可以重叠。所以简单地计算下一个间隔的开始减去这个间隔的结束是行不通的......考虑这个例子：[1,5] [2,4] [6,10] [6,8]

Answer 1

<?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自身相减，并找到最大差距。