一道百度算法面试题:区间集合合并
嘻嘻发布于2020-08-15
最后更新于2020年7月25日
浏览百度的面试过程中经常会出现现场算法的实现,这个算法可能是一个不负责的算法,考察现在编码的能力,所以不用担心,只有你冷静下来一定实现出来,记得一定要用自己最熟悉的语言。
以下这道区间合并算法题,来源一个朋友百度的一面:
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
PHP编码实现:
<?php
//$data=[[1,3],[2,6],[8,10],[15,18]];
//$data = [[1,3],[2,6]];
//$data = [[1,4],[4,5]];
$data = [[1,10], [2,6]];
if (!is_array($data)|| empty($data)) {
return [];
}
//filter array
$data = array_filter($data, function($item) {
return !empty($item);
});
//sort array
usort($data, function($a, $b){
return $a[0] > $b[0];
});
$resutls = [];
$current = array_shift($data);
while(!empty($data)) {
$next = array_shift($data);
list($curMin, $curMax) = $current;
list($nextMin, $nextMax) = $next;
if ($curMax >= $nextMin) {
$current = [min($curMin, $nextMin), max($curMax,$nextMax)];
} else {
$results[] = $current;
$current = $next;
}
}
$results[] = $current;
print_r($results);