php - 查找多个间隔之间的最长间隔

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 本身减去最后的结束时间，并找到最大差距。