Merging overlapping ranges in PHP arrays?
Untested, but the idea here is to sort the data first by the first element, then merge subsequent elements with the previous one as long as possible.
usort($data, function($a, $b)
{
return $a[0] - $b[0];
});
$n = 0; $len = count($data);
for ($i = 1; $i < $len; ++$i)
{
if ($data[$i][0] > $data[$n][1] + 1)
$n = $i;
else
{
if ($data[$n][1] < $data[$i][1])
$data[$n][1] = $data[$i][1];
unset($data[$i]);
}
}
$data = array_values($data);
PHP combine two seperate conflicting date ranges into unique pairs
Usage : $output = mergeRanges($input);
This method is originally designed to merge any kind on numeric ranges, timestamps included and supports any kind of overlaps. It takes an array of objects in input, containing "from" and "to" keys which is customizable.
/**
* @param $ranges
* @param string $keyFrom
* @param string $keyTo
*
* @return array
*/
function mergeRanges($ranges, $keyFrom = 'from', $keyTo = 'to')
{
// Split from / to values.
$arrayFrom = [];
$arrayTo = [];
foreach ($ranges as $date)
{
$arrayFrom[] = $date->$keyFrom;
$arrayTo[] = $date->$keyTo;
}
// Sort ASC.
natsort($arrayFrom);
natsort($arrayTo);
$ranges = [];
// Iterate over start dates.
foreach ($arrayFrom as $indexFrom => $from)
{
// Get previous entry.
$previousEntry = end($ranges);
// Find associated default "to" value to "from" one.
$to = $arrayTo[$indexFrom];
// If we have a previous entry and "to" is greater than
// current "from" value.
if (isset($previousEntry->to) && $from < $previousEntry->to + 1)
{
// Do nothing if this range is completely covered
// by the previous one.
if ($to > $previousEntry->to)
{
// We just change te "to" value of previous range,
// so we don't create a new entry.
$previousEntry->to = $to;
}
}
else
{
// Create a new range entry.
$ranges[] = (object) [
$keyFrom => $from,
$keyTo => $to,
];
}
}
return $ranges;
}
$input = [
// One day.
(object) [
'title' => 'One day.',
'from' => 1560816000,
'to' => 1560902399,
],
// Same day, inner period
(object) [
'title' => 'Same day, inner period',
'from' => 1560816000 + 1000,
'to' => 1560902399 - 1000,
],
// Just before midnight
(object) [
'title' => 'Just before midnight',
'from' => 1560816000 - 1000,
'to' => 1560816000 + 1000,
],
// Just after midnight
(object) [
'title' => 'Just after midnight',
'from' => 1560902399 - 1000,
'to' => 1560902399 + 1000,
],
// Other period before
(object) [
'title' => 'Other period before',
'from' => 1560902399 - 100000,
'to' => 1560902399 - 100000 + 5000,
],
// Other period after
(object) [
'title' => 'Other period after',
'from' => 1560816000 + 100000,
'to' => 1560902399 + 100000 + 5000,
],
];
Array
(
[0] => Array
(
[from] => 2019-06-17 22:13:19
[to] => 2019-06-17 23:36:39
)
[1] => Array
(
[from] => 2019-06-18 01:43:20
[to] => 2019-06-19 02:16:39
)
[2] => Array
(
[from] => 2019-06-19 05:46:40
[to] => 2019-06-20 07:09:59
)
)
Return the amount of overlapping from arraylist of date intervals
I found out the way you treat the dates. So there's no need to convert them to the float number. So the question is about algorithms. The following code could be a solution.
$all_data = [
'Chevenez' => [
'41.NEwan0' => [['2022-01-19 03:53:37.49459', '2022-01-19 04:53:37.49459'],
['2022-01-09 03:53:37.49459', '2022-01-09 04:53:37.49459']],
'41.NEwan1' => [['2022-01-19 04:23:37.49459', '2022-01-19 05:23:37.49459'],
['2022-01-09 04:23:37.49459', '2022-01-09 05:23:37.49459']],
'42.NEwan0' => [['2022-01-19 04:03:37.49459', '2022-01-19 04:33:37.49459'],
['2022-01-09 04:03:37.49459', '2022-01-09 04:33:37.49459']],
'42.NEwan1' => [['2022-01-19 04:13:37.49459', '2022-01-19 05:13:37.49459'],
['2022-01-09 04:13:37.49459', '2022-01-09 05:13:37.49459']],
'43.NEwan0' => [['2022-01-09 03:53:37.49459', '2022-01-09 04:53:37.49459']],
'43.NEwan1' => [['2022-01-09 04:23:37.49459', '2022-01-09 05:23:37.49459']],
'44.NEwan0' => [['2022-01-09 04:03:37.49459', '2022-01-09 04:33:37.49459']],
'44.NEwan1' => [['2022-01-09 04:28:37.49459', '2022-01-09 05:13:37.49459']],
],
'Barcelona' => [
'5.NEwan0' => [['2022-01-19 03:53:37.49459', '2022-01-19 04:53:37.49459']],
'5.NEwan1' => [['2022-01-19 04:23:37.49459', '2022-01-19 05:23:37.49459']],
'16.NEwan0' => [['2022-01-19 04:03:37.49459', '2022-01-19 04:33:37.49459']],
'16.NEwan1' => [['2022-01-19 04:13:37.49459', '2022-01-19 05:13:37.49459']]
]
];
$periods = [];
foreach($all_data as $place => $parts) {
// select first times of each place
$part1_times = $parts[array_key_first($parts)];
$periods[$place] = [];
// walk on times parts
foreach($part1_times as $t => $part1_time_range) {
$range_low = $part1_time_range[0];
$range_up = $part1_time_range[1];
// detect common range
foreach($parts as $part_times) {
if(!isset($part_times[$t])) break;
$rlow = $part_times[$t][0];
$rup = $part_times[$t][1];
if($rlow > $range_low) $range_low = $rlow;
if($rup < $range_up) $range_up = $rup;
}
if($range_low < $range_up) $periods[$place][] = [$range_low, $range_up];
}
// sort times in each place from small to big
usort($periods[$place], function($a, $b) {
return $a[0] > $b[0] ? 1 : -1;
});
}
// Output the answer in the specified format.
foreach ($periods as $key => $periods) {
foreach ($periods as $period) {
echo "$key : $period[0] -> $period[1]\n";
}
}
Chevenez : 2022-01-09 04:23:37.49459 -> 2022-01-09 04:33:37.49459
Barcelona : 2022-01-19 04:23:37.49459 -> 2022-01-19 04:33:37.49459
Algorithm to combine / merge date ranges
Sort by start date.
Then iterate through and check for if the next item's start date is before or directly after the current one's end date. If it is, then merge the next one into the current one. Then continue.
PHP merge two array with range
Thanks everyone idea.
I just come up with the code and post it here in case if someone have the same problem, they could make reference to.
I first combine the $a and $b to a single array $tmp_combine and sort them according to 'begin'.
Construct an unique sorted index array $ind containing all 'start' and 'end' of the $tmp_combine.
Then calculate the min value for each index point pair from $tmp_combine, construct an array $ind_SR.
for number of item in $ind_SR, do the merge if they have the same value consecutively and output the final answer to $result.
$tmp_combine = array_orderby(array_merge($a,$b), 'begin', SORT_ASC);
$ind = array_merge(array_column($tmp_combine, 'begin'),array_column($tmp_combine, 'end'));
$ind = array_unique($ind);
asort($ind);
$ind = array_values($ind);
$index = 0;
$ch_now = $ind[0];
for ($i=0; $i<count($ind)-1; $i++){ //calculate the mid pt min value
$mid_pt = ($ind[$i] + $ind[$i+1]) /2;
array_push($ind_SR, find_min_SR($tmp_combine,$mid_pt));
}
for ($i=0; $i<count($ind_SR); $i++){
if ($ch_now <= $ind[$i]){
$start = $ind[$i];
$end = $ind[$i+1];
$result[$index]['begin'] = $ind[$i];
for ($j=$i; $j<count($ind_SR); $j++){
$start_j = $ind[$j];
$end_j = $ind[$j+1];
if ($ind_SR[$j] == $ind_SR[$i]){
$result[$index]['begin'] = $start;
$result[$index]['end'] = $end_j ;
$result[$index]['value'] = $ind_SR[$i];
$ch_now = $ind[$j+1];
} else{
$result[$index]['end'] = $ind[$j] ;
break; break;
}
}
$index++;
}
PHP: Define a variable within two or more ranges with alternatives to array_merge()?
You can merge the original range() with the new range, and assign it back to $x. You do not have to give it a new name for every new value it gets, you can overwrite the value instead.
$x = range(0,10);
$x = array_merge($x, range(15,30));
print_r($x);
How to check overlapping among multiple date ranges in PHP?
<?php
// pass your ranges to this method and if there is a common intersecion it will
// return it or false
function checkIfOverlapped($ranges)
{
$res = $ranges[0];
$countRanges = count($ranges);
for ($i = 1; $i < $countRanges; $i++) {
$r1s = $res['start'];
$r1e = $res['end'];
$r2s = $ranges[$i]['start'];
$r2e = $ranges[$i]['end'];
if ($r1s >= $r2s && $r1s <= $r2e || $r1e >= $r2s && $r1e <= $r2e || $r2s >= $r1s && $r2s <= $r1e || $r2e >= $r1s && $r2e <= $r1e) {
$res = array(
'start' => $r1s > $r2s ? $r1s : $r2s,
'end' => $r1e < $r2e ? $r1e : $r2e
);
} else return false;
}
return $res;
}
// example
$ranges = array(
array('start' => '2014-01-01', 'end' => '2014-01-05'),
array('start' => '2014-01-05', 'end' => '2014-01-10'),
array('start' => '2014-01-04', 'end' => '2014-01-07')
);
var_dump(checkIfOverlapped($ranges));
Identity the available range numbers when two range numbers are overlap
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.
Exclude date/time ranges from an array of date/time ranges with overlapping
Create common list of pairs {time; flag}, where flag is time_start, time_end, restriction_start or restriction_end.
Sort this list by time. In case of tie use flag as secondary key (for example, restr_start should go after time_end).
Make $Active=0, $Exclude=0
Walk through sorted list.
When you meet time_start, increment value of $Active {1}
When you meet time_end, decrement value of $Active {2}
When you meet restriction_start, increment value of $Exclude {3}
When you meet restriction_end, decrement value of $Exclude {4}
Open output interval in the next cases:
{1}: $Active becomes 1 and $Exclude = 0
{4}: $Exclude becomes 0 and $Active is non-zero
Close output interval in the next cases:
{2} $Active becomes 0 and $Exclude = 0
{3} $Exclude becomes 1 and $Active is non-zero
example: (don't know exact php syntax for complex conditions)
case $TimeStart:
$active = $active + 1;
if ($active=1) and ($exclude=0)
$range['start_time'] = $mergedTime['time'];
break;
....
case $RestrictionEnd:
$exclude = $exclude - 1;
if ($exclude=0) and ($active > 0)
$range['start_time'] = $mergedTime['time'];
break;
Related Topics
Send Zip File to Browser/Force Direct Download
Using Moodle Create Users and Enroll Them in Courses via SQL
Paypal Ipn Bad Request 400 Error
PHP Resize Image on or Before Upload
Does HTML_Entity_Decode Replaces &Nbsp; Also? If Not How to Replace It
Str_Replace() for Multiple Value Replacement
Unchecked Checkbox Returning Null Value
What Is an Appropriate Content-Type Header for JavaScript Files
SQL Select * from Multiple Tables
MySQL Insert ....On Duplicate Update - Adds One to the Autoincrement
Facebook Graph API - Friends Using Application