当两个范围编号重叠时，标识可用的范围编号

Question

If I have an existing range:

1-10
11-50

Then I will enter a new range from 1 - 60, How could I detect that the new range to be added overlaps to the previous entries? And how can I get the available range? In this case the available range is from 51-60.

Does anyone here have a great idea on this?

Thanks for helping.

Here's my current code:

$saved = array(
                            array(
                                    "start" => 1,
                                    "end"   => 10
                                ),
                            array(
                                    "start" => 10,
                                    "end"   => 50
                            )
                        );
            $new_range = array(
                                "start" => 1,
                                "end"   => 60
                            );
            $usable_range = array();
            $previous_from = 0;
            $previous_to = 0;
            foreach($saved as $value)
            {
                $range_start = 0;
                $range_end = 0;
                if($previous_from<$value['start'])
                {
                    $previous_from = $value['start'];
                }
                if($previous_to<$value['end'])
                {
                    $previous_to = $value['end'];
                }
                if($previous_from<=$new_range['start'])
                {
                    if($previous_to<$new_range['end'])
                    {
                        $range_start = $previous_to+1;
                        $range_end   = $new_range['end'];
                        $new_range['start'] = $range_start;
                    }
                 }
                else if($previous_from>=$new_range['start'])
                {
                    if($previous_to<$new_range['end'])
                    {
                        $range_start = $previous_to+1;
                        $range_end   = $new_range['end'];
                        $new_range['start'] = $range_start;
                    }
                }
                $usable[] =     array("range_start"=>$range_start,"range_end"=>$range_end);             
            }

Answer 1

Call every interval (min,max)

1) Sort your list of intervals by their min.

2) Check to see if any max is greater than the next entry over's min. If they are, create the interval that is the smaller of their mins and the greater of their maxes, and add it back into the list in place of those two.

3) Whenever you get a new interval, binary search into the list to add it, sorted by min. Then, using similar logic as in 2), attempt to merge it with the entry one below and one above until no more merges are possible.

---

EDIT: A few changes.

First, since we're using integers not floats, if you have an interval like 1,10 and 11,20 then there is no 'gap' between the 10 and 11 - so we should consider this to be one larger interval, 1,20. Reflect this by, instead of checking to see if max > next min, if max >= next min - 1.

Second, if you want to find all intervals formed by overlap when merging a new interval into your list of intervals:

1) Since your list of intervals is known to be in a state where it is sorted by min and also sorted by max, binary search into it to find the lowest min just above your new min and the highest max just above your new max.

2) Iterate over min, max, min, max... etc in your array that are between your new min and new max. Below the lowest min, above the highest max and between each max/min you can compute the interval that is in the 'gap' there, and return them in e.g. an array.

---

For example if your list of intervals contains 13,16, 21,24 and 31, 38 and you want to calculate the non-overlap of the new interval 1,30:

1) We binary search into our list and find that 13 is the lowest min above 1 and 24 is the highest max above 30.

2) We iterate like so:

• Between our min and the lowest min is 1 and 13 - so this forms an interval 1,12 (inclusive bottom, exclusive top). Add onto the return array.
• Between max and the next min is 16 and 21 - so this forms an interval 17,20 (exclusive on both ends). Add onto the return array.
• Between max and our max is 24 and 30 - so this forms an interval 25,30 (exclusive bottom, inclusive top). Add onto the return array.