場景
用戶輸入若干個(gè)區(qū)間范圍[X1,Y1],[X2,Y2],[X3,Y3],[Xn,Yn]...,其中X1-Xn,Y1-Yn均為任意數(shù)字且前者小于后者(X1<Y1...).
例如:[-1,1.1],[1.1,15],[19,22] 不存在重合區(qū)間.[1,11],[11,15],[14,22] 則存在重合區(qū)間.
思路
1.將所有的點(diǎn)落在同一條軸上,排序(有可能點(diǎn)會(huì)重復(fù)覆蓋)
2.統(tǒng)計(jì)坐標(biāo)軸上的點(diǎn)出現(xiàn)在某個(gè)范圍的次數(shù),可能為(0,1,2),0表示所有的點(diǎn)都被覆蓋,1表示被覆蓋一個(gè),2表示沒有被覆蓋
3.對排好序的坐標(biāo)軸進(jìn)行遍歷比較
4.這里查找次數(shù)為2的點(diǎn)進(jìn)行比較,如果為2則表示下一個(gè)坐標(biāo)點(diǎn)必為某個(gè)范圍的最大值,否則就是有區(qū)間重合
用PHP實(shí)現(xiàn)代碼如下:
<?php
function checkRange($list)
{
$range = [];
foreach ($list as $key => $value) {
$range["{$value[0]}"] = $key;
$range["{$value[1]}"] = $key;
}
ksort($range);
$count = array_count_values($range);
$len = count($range);
for ($i = 0; $i < $len; $i++) {
$value = current($range);
if ($count[$value] == 2) {
next($range);
$next_key = key($range);
if ($list[$value][1] != $next_key) {
return false;
}
$i++;
}
next($range);
}
return true;
}
$list = [[-1,2.5],[3.5,9],[9,10.1],[10.1,12.1],[12,34],[56,777],[777,999]];
var_dump(checkRange($list)); //bool(false)
以上就是實(shí)現(xiàn)的全過程,有問題歡迎指正.不連續(xù)區(qū)間重合判斷
