连续区间重合判断

场景

客户输入若干个区间范围[X₁,Y₁],[X₂,Y₂],[X₃,Y₃],[X_n,Y_n]…,其中X₁-X_n,Y₁-Y_n均为任意数字且前者小于后者(X₁<Y₁…).

例如:[-1,1.1],[1.1,15],[19,22] 不存在重合区间.[1,11],[11,15],[14,22] 则存在重合区间.

思路

1.将所有的点落在同一条轴上,排序(有可能点会重复覆盖)

2.统计坐标轴上的点出现在某个范围的次数,可能为(0,1,2),0表示所有的点都被覆盖,1表示被覆盖一个,2表示没有被覆盖

3.对排好序的坐标轴进行遍历比较

4.这里查找次数为2的点进行比较,假如为2则表示下一个坐标点必为某个范围的最大值,否则就是有区间重合

用PHP实现代码如下:

<?phpfunction 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)

以上就是实现的全过程,有问题欢迎指正.不连续区间重合判断