If I have the following array of objects with start and end dates, how can I best calculate the maximum number of ranges that overlap each other? I just want the count for the highest number of overlapping ranges. e.g. my example below the highest number of overlapping ranges would be 3.
[
{ start_date: '2021-01-01 10:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 08:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 12:00:00', end_date: '2021-01-01 14:00:00'},
{ start_date: '2021-01-01 12:30:00', end_date: '2021-01-01 14:30:00'},
{ start_date: '2021-01-01 14:00:00', end_date: '2021-01-01 17:30:00'},
]
Two elements of the list overlap if Math.max(start_1, start_2) < Math.min(end_1, end_2).
I'm unsure of your counting requirement for the number of overlapping time segments, but this should get you on the right path.
const list = [
{ start_date: '2021-01-01 10:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 08:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 12:00:00', end_date: '2021-01-01 14:00:00'},
{ start_date: '2021-01-01 12:30:00', end_date: '2021-01-01 14:30:00'},
{ start_date: '2021-01-01 14:00:00', end_date: '2021-01-01 17:30:00'},
];
// Step 1 : Convert to Date objects
const dt_list = list.map((currItem) => {
return [new Date(currItem.start_date), new Date(currItem.end_date)];
});
// Map over arrays of Date values
const result = dt_list.map((item, index) => {
let count = 0;
// Count overlaps with remainder of list
for (let i=(index + 1); i < dt_list.length; i++) {
if (Math.max(item[0], dt_list[i][0]) < Math.min(item[1], dt_list[i][1]))
count += 1;
}
return count;
}).reduce((sum, current) => {
return sum + current;
}, 0);
console.log(result); // 3
Assuming your date format is always YYYY-MM-DD hh:mm:ss, you can use string comparisons for comparing the date/times. If other formats are possible as well, I would suggest using some library like Moment.js.
You could loop over the ranges and check for each range whether it overlaps another one, like:
const ranges = [
{ start_date: '2021-01-01 10:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 08:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 12:00:00', end_date: '2021-01-01 14:00:00'},
{ start_date: '2021-01-01 12:30:00', end_date: '2021-01-01 14:30:00'},
{ start_date: '2021-01-01 14:00:00', end_date: '2021-01-01 17:30:00'},
];
let overlaps = 0;
for (let i = 0; i < ranges.length; i++) {
const range1 = ranges[i];
for (let j = i + 1; j < ranges.length; j++) {
const range2 = ranges[j];
if (!(range1.start_date >= range2.end_date
|| range2.end_date <= range1.start_date
|| range2.start_date >= range1.end_date
|| range1.end_date <= range2.start_date)) {
console.log(JSON.stringify(ranges[i]) + ' overlaps ' + JSON.stringify(ranges[j]));
overlaps++;
}
}
}
console.log('Overlaps: ' + overlaps); // Overlaps: 3You could convert all the dates to timeStamps ( seconds since 1970/01/01 ) for better comparison. Then push all of them into a new array converted_dates[] to use them inside a double loop where a conditional statement its implemented to see if there is an overlap between any of the ranges.
This code should work with any date and any time, keeping in mind, that to do so, it should maintain the date format of the original range array.
const ranges = [
{ start_date: '2021-01-01 10:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 08:00:00', end_date: '2021-01-01 11:00:00'},
{ start_date: '2021-01-01 12:00:00', end_date: '2021-01-01 14:00:00'},
{ start_date: '2021-01-01 12:30:00', end_date: '2021-01-01 14:30:00'},
{ start_date: '2021-01-01 14:00:00', end_date: '2021-01-01 17:30:00'},
];
const converted_dates = [];
for(let range of ranges){
var start_sliced_date = range.start_date.slice(0,10);
var start_sliced_hour = range.start_date.slice(11,19);
var end_sliced_date = range.end_date.slice(0,10);
var end_sliced_hour = range.end_date.slice(11,19);
// Create a date object to use getTime() method
let newDate = new Date(start_sliced_date + "T" + start_sliced_hour);
let start_timeStamp = newDate.getTime()/1000;
newDate = new Date(end_sliced_date + "T" + end_sliced_hour);
let end_timeStamp = newDate.getTime()/1000;
// Create a new array with the dates converted to timeStamps
converted_dates.push({
"start": start_timeStamp,
"end": end_timeStamp
});
}
var count = 0;
for(var i = 0; i < converted_dates.length; i++){
let end = converted_dates[i].end;
for(var pos = i + 1; pos < converted_dates.length; pos++){
let otherStart = converted_dates[pos].start;
// Is there an overlap?
if(end>otherStart){
count++,
console.log('Overlap of range ' + (i + 1) + ' with ' + (pos + 1));
}
}
}
console.log('Total number of overalped ranges: ' + count);