Finding the longest gap between multiple intervals

Updated Solution :-

$intervals = [
    [1,2],
    [2,2],
    [5,6],
    [8,10]
];
$rr = [];
foreach($intervals as $v){
    $rr[] = range($v[0],$v[1]);
}
$n = 10;
$range      = range(1,$n);
$diff =     array_diff($range,array_values(array_unique(array_merge(...$rr))));
$r = groupConsecutive($diff);

$max = 0;
if (count($r)) {
    foreach ($r as $gap) {
        $length = 1;
        if (is_array($gap)) $length = count($gap);
        if ($max < $length) $max = $length;
    }
}

echo $max;

function  groupConsecutive($array) {
   $ret  = array();
   $temp = array();
   foreach($array as $val) {
      if(next($array) == ($val + 1))
         $temp[] = $val;
      else
         if(count($temp) > 0) {
            $temp[] = $val;
            $ret[]  = $temp;
            $temp   = array();
         }
         else
            $ret[] = $val;
   }
   return $ret;
}

DEMO

<?php

$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10]
];

$non_overlapping = [];
$start = -1;
$end = -1;

foreach($intervals as $index => $interval){
    if($start == -1) $start = $interval[0];
    if($end == -1) $end = $interval[1];

    if($index == 0) continue; // since it's first index

    if($interval[0] >= $end){
        $non_overlapping[] = [$start,$end];
        $start = $interval[0];
        $end = $interval[1];
    }else{
        $end = max($end,$interval[1]);
    }
}

$non_overlapping[] = [$start,$end];
$maximum_gap = 0;
$prev_end = 0;

foreach($non_overlapping as $index => $interval){
    $maximum_gap = max($maximum_gap,$interval[0] - $prev_end - 1);
    $prev_end = $interval[1];
}

$maximum_gap = max($maximum_gap,$n - $prev_end);

echo $maximum_gap;

• Since your intervals are sorted according to start time, we make a new array of non overlapping intervals.
• Now, we just subtract new start time with previous end time and at last also, last end time with $n itself and find the maximum gap.

If the partitions are sorted (like in your example). You can iterate over the partitions and create a new array containing:

• The original postion of the interval in the first array
• The distance of the first element of the partition and the last element of the previous partition.

With that you will have a list of gaps between partitions. Then you simply sort those gaps and take the last one.

But as I've said this is assuming that your partitions are sorted.

There an example then you sort $gaps by second element of the value and take the last one.

<?php                                                                                                                                                                                                                                                         

$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10],
];

$gaps = array();

$prev_range_max = 1;
for ($i = 0; $i < count($intervals); $i++) {
    $gaps[] = Array($i, $intervals[$i][0] - $prev_range_max);
    $prev_range_max = $intervals[$i][1];
}

I am describing an approach that will be much efficient-

1. If the intervals are unsorted according to the start time- First sort the array of intervals based on the start time. Worst case complexity O(nlogn). if its sorted then we don't have to do anything.

2. Iterate through the sorted interval array from the second element and each iteration if the start time is greater than the end time of last interval - calculate the difference .

3. Find out the max difference comparing the difference in each iteration.

   Complexity- Unsorted Array- O(nlogn)+ O(n) Sorted Array- O(n).

pseudo code--

example--

We can have a simple, O(n) time O(1) space, algorithm to keep track of the interval we are in as we iterate over the intervals sorted by start position. The current interval starts with:

left = interval[0][0]
right = interval[0][1]
i = 1 // pointer
n = list length
max_gap = 0

Then,

while i < n and interval[i][0] <= right:
  // update right
  right = max(right, interval[i][1])
  i = i + 1

Now we are either at the end of the list if there were no gaps, or we are at a new interval that started at least at (right + 1) (which I think in your case wouldn't qualify as a gap).

So here update the current largest gap and repeat the while routine.

max_gap = max(
  max_gap,
  interval[i][0] - right - 1
)
left = interval[i][0]
right = interval[i][1]

JavaScript example:

function f(A){
  console.log(JSON.stringify(A))
  let left = A[0][0]
  let right = A[0][1]
  console.log(`i: 0, (${ left }, ${ right })`)
  let i = 1 // pointer
  let n = A.length
  let max_gap = 0

  while (i < n){
    while (i < n && A[i][0] <= right){
      // update right
      right = Math.max(right, A[i][1])
      console.log(`i: ${ i }, (${ left }, ${ right })`)
      i = i + 1
    }

    if (i < n){
      max_gap = Math.max(
        max_gap,
        A[i][0] - right - 1
      )
      console.log(`i: ${ i }, max_gap: ${ max_gap }`)
      left = A[i][0]
      right = A[i][1]
    }
  }

  return max_gap
}

let examples = [
  [[1,5], [2,4], [6,10], [6,8]],
  [[1, 2], [2, 2], [5, 6], [8, 10]],
  [[2,4], [5,8], [9,10]],
  [[1,1], [5,6], [9,10]]
]

for (let ex of examples)
  console.log(`result: ${ f(ex) }\n\n`)