一道百度算法面试题:区间集合合并

百度的面试过程中经常会出现现场算法的实现,这个算法可能是一个不负责的算法,考察现在编码的能力,所以不用担心,只有你冷静下来一定实现出来,记得一定要用自己最熟悉的语言。

以下这道区间合并算法题,来源一个朋友百度的一面:

给出一个区间的集合,请合并所有重叠的区间。
示例 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);
shell脚本是什么
linux中的用户管理
ajax-loader