查找多个间隔之间的最长间隔
查找多个间隔之间的最长间隔
提问于 2019-06-23 18:24:27
假设您有一个变量$n，表示时间轴上的多个分区，以及一个可变长度的间隔数组：
$n = 10;
$intervals = [
[1, 2],
[2, 2],
[5, 6],
[8, 10],
];问题是要在时间线上找到这些间隔之间的最大间隔。对于上面的问题，我们有两个长度为2和1的空格，所以答案应该是2。为了更好地可视化它：
我的直截了当的方法效率不高。
- 初始化一个长度为$n的空时间线数组，每个元素都设置为'E‘，就像在empty中一样。
- 在每个时间间隔内循环，并创建另一个从间隔开始到时间间隔结束的for循环，并将时间线数组中的这些元素设置为'T’，就像在taken中一样。
- 循环时间线数组，并启动一个每个连续的'E‘字符递增的$counter，然后如果它的值大于前一个，则将其值保存到变量$max中。
我可以做哪些改进？
请注意：
时间间隔总是根据它们的开始进行排序的，positions.
- Intervals不一定要从时间轴的开头开始，也不一定要在时间轴的末尾结束。因此，在第一个间隔之前可能存在间隙，而在最后一个interval.
- Intervals之后可能存在间隙。因此，简单地计算下一个间隔的开始减去这个间隔的结束是行不通的…考虑这个例子: 1,5，6,10
回答 5
Stack Overflow用户
回答已采纳
发布于 2019-06-23 22:07:16
<?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本身减去最后的结束时间，就可以找到最大的差距。
Stack Overflow用户
发布于 2019-06-23 19:01:42
更新的解决方案:-
$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;
}Stack Overflow用户
发布于 2019-06-23 19:04:03
是否对分区进行了排序(如示例中所示)。您可以遍历分区并创建一个包含以下内容的新数组：
- 该间隔在第一个数组中的原始位置
- 该分区的第一个元素与前一个分区的最后一个元素的距离。
这样你就有了一个分区之间的空隙列表。然后，您只需对这些空格进行排序，并采用最后一个空格。
但正如我已经说过的，这是假设您的分区是排序的。
这里有一个示例，然后按值的第二个元素对$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];
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56722946
复制相关文章
相似问题
腾讯云开发者
