$intervals Any intervals. * @return array */ public static function normalize( array $intervals ): array { $list = array(); foreach ( $intervals as $interval ) { $start = (int) $interval[0]; $end = (int) $interval[1]; if ( $end > $start ) { $list[] = array( $start, $end ); } } usort( $list, static fn( array $a, array $b ): int => array( $a[0], $a[1] ) <=> array( $b[0], $b[1] ) ); $out = array(); foreach ( $list as $interval ) { $last = count( $out ) - 1; if ( $last >= 0 && $interval[0] <= $out[ $last ][1] ) { $out[ $last ][1] = max( $out[ $last ][1], $interval[1] ); } else { $out[] = $interval; } } return $out; } /** * Everything in either list. * * @param array $a Intervals. * @param array $b Intervals. * @return array */ public static function union( array $a, array $b ): array { return self::normalize( array_merge( $a, $b ) ); } /** * What is in both lists. * * @param array $a Intervals. * @param array $b Intervals. * @return array */ public static function intersect( array $a, array $b ): array { $a = self::normalize( $a ); $b = self::normalize( $b ); $out = array(); $i = 0; $j = 0; $na = count( $a ); $nb = count( $b ); while ( $i < $na && $j < $nb ) { $start = max( $a[ $i ][0], $b[ $j ][0] ); $end = min( $a[ $i ][1], $b[ $j ][1] ); if ( $end > $start ) { $out[] = array( $start, $end ); } if ( $a[ $i ][1] < $b[ $j ][1] ) { ++$i; } else { ++$j; } } return $out; } /** * What is in the first list and not in the second. * * @param array $from Intervals to cut. * @param array $remove Intervals to cut out. * @return array */ public static function subtract( array $from, array $remove ): array { $remove = self::normalize( $remove ); $out = array(); foreach ( self::normalize( $from ) as $interval ) { $start = $interval[0]; foreach ( $remove as $cut ) { if ( $cut[1] <= $start ) { continue; } if ( $cut[0] >= $interval[1] ) { break; } if ( $cut[0] > $start ) { $out[] = array( $start, $cut[0] ); } $start = max( $start, $cut[1] ); if ( $start >= $interval[1] ) { break; } } if ( $start < $interval[1] ) { $out[] = array( $start, $interval[1] ); } } return $out; } /** * Whether [start, end) lies wholly inside one of the intervals. * * @param array $intervals Normalized intervals. * @param int $start Start. * @param int $end End. */ public static function contains( array $intervals, int $start, int $end ): bool { foreach ( $intervals as $interval ) { if ( $interval[0] <= $start && $end <= $interval[1] ) { return true; } if ( $interval[0] > $start ) { return false; } } return false; } /** * Whether two intervals overlap. * * @param int $a_start First start. * @param int $a_end First end. * @param int $b_start Second start. * @param int $b_end Second end. */ public static function overlap( int $a_start, int $a_end, int $b_start, int $b_end ): bool { return $a_start < $b_end && $b_start < $a_end; } /** * Total seconds covered. * * @param array $intervals Intervals. */ public static function length( array $intervals ): int { $total = 0; foreach ( self::normalize( $intervals ) as $interval ) { $total += $interval[1] - $interval[0]; } return $total; } }