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'},
]

CodePudding user response：

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

CodePudding user response：

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: 3

CodePudding user response：

You 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 shifts.

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 shifts array.

Try the following snippet

const shifts = [
  { 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 = [];

// Convert to timestamps
for(let shift of shifts){
  var start_sliced_date = shift.start_date.slice(0,10);
  var start_sliced_hour = shift.start_date.slice(11,19);
  var end_sliced_date = shift.end_date.slice(0,10);
  var end_sliced_hour = shift.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 shift '   (i   1)   ' with '   (pos   1));
    }
  }
}

console.log('Total number of overalped shifts: '   count);