连续区间重合判断

场景

用户输入若干个区间范围[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实现代码如下:

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

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