Combining intersecting objects with interval attributes in an array using javascript

Question

Combining intersecting objects with interval attributes in an array using javascript

I have encountered similar questions, however, the provided answers do not resolve my specific issue.

The data I have is an array of range objects, each with the following properties:

start: Integer, indicating the start of the range,
end: Integer, indicating the end of the range.

The desired output is:

An array of non-overlapping range objects that cover the same ranges as the input, sorted from the smallest start to the largest start. Two ranges do not overlap if:

range1.start <= range2.start, and
range1.end >= range2.start

Input:

[
  { start: 8, end: 10 },
  { start: 5, end: 7  },
  { start: 9, end: 12 },
  { start: 2, end: 6  },
]

Output:

 [
   { start: 2, end: 7  },
   { start: 8, end: 12 }
 ]

I have attempted various solutions found online for merging overlapping intervals, but they have not provided the desired result.

Thank you.

javascript arrays object

Answer 1

Answer №1

To efficiently handle overlapping ranges, one approach is to sort the array based on the start and end values. Then, iterate through the sorted array and check for any overlapping ranges.

var data = [{ start: 8, end: 10 }, { start: 5, end: 7 }, { start: 9, end: 12 }, { start: 2, end: 6 }],
    result = data
        .sort(function (a, b) { return a.start - b.start || a.end - b.end; })
        .reduce(function (r, a) {
            var last = r[r.length - 1] || [];
            if (last.start <= a.start && a.start <= last.end) {
                if (last.end < a.end) {
                    last.end = a.end;
                }
                return r;
            }
            return r.concat(a);
        }, []);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

To efficiently handle overlapping ranges, one approach is to sort the array based on the start and end values. Then, iterate through the sorted array and check for any overlapping ranges.

var data = [{ start: 8, end: 10 }, { start: 5, end: 7 }, { start: 9, end: 12 }, { start: 2, end: 6 }],
    result = data
        .sort(function (a, b) { return a.start - b.start || a.end - b.end; })
        .reduce(function (r, a) {
            var last = r[r.length - 1] || [];
            if (last.start <= a.start && a.start <= last.end) {
                if (last.end < a.end) {
                    last.end = a.end;
                }
                return r;
            }
            return r.concat(a);
        }, []);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

Answer №2

var intervals = [
  { start: 8, end: 10 },
  { start: 5, end: 7  },
  { start: 9, end: 12 },
  { start: 2, end: 6  }
];


function mergeIntervals(intervals) {
  // sort the intervals based on start value
  intervals.sort((a, b) => a.start - b.start);
  
  // function to merge two intervals
  var mergeFn = (a, b) => ({start: Math.min(a.start, b.start), end: Math.max(a.end, b.end)});
  
  // function to check if two intervals overlap
  var overlapFn = (a, b) => (b.start <= a.end);
  
  var current = intervals[0];
  var result = [];
  for(var i = 1; i < intervals.length; i++) {
    if(overlapFn(current, intervals[i])) 
       current = mergeFn(current, intervals[i]);
    else {
      result.push(current);
      current = intervals[i];
    }
  }
  result.push(current);

  return result;
}

console.log(mergeIntervals(intervals));

Answer 4

var intervals = [
  { start: 8, end: 10 },
  { start: 5, end: 7  },
  { start: 9, end: 12 },
  { start: 2, end: 6  }
];


function mergeIntervals(intervals) {
  // sort the intervals based on start value
  intervals.sort((a, b) => a.start - b.start);
  
  // function to merge two intervals
  var mergeFn = (a, b) => ({start: Math.min(a.start, b.start), end: Math.max(a.end, b.end)});
  
  // function to check if two intervals overlap
  var overlapFn = (a, b) => (b.start <= a.end);
  
  var current = intervals[0];
  var result = [];
  for(var i = 1; i < intervals.length; i++) {
    if(overlapFn(current, intervals[i])) 
       current = mergeFn(current, intervals[i]);
    else {
      result.push(current);
      current = intervals[i];
    }
  }
  result.push(current);

  return result;
}

console.log(mergeIntervals(intervals));

Combining intersecting objects with interval attributes in an array using javascript

Answer №1

Answer №2

Similar questions

Can you explain the concepts of 'theme' and 'classes'?

Unable to load module/controller file from Angular 1 into view/html

A step-by-step guide on how to use ajax/jquery to access an external webpage without relying on iframe

The anchor link is not aligning properly due to the fluctuating page width

Tips for passing a parameter (such as an ID) through a URL using ng-click to display a subdocument belonging to a particular user in

How to resolve the issue of not being able to access functions from inside the timer target function in TypeScript's

Recording audio using Cordova and Javascript

Using Typescript to import an npm package that lacks a definition file

Material UI: Easily adjusting font size within Lists

Utilizing nested JSON data with React

Listening to sound from a specific table cell retrieved from an array generated by a Struct

Leveraging the (click) event within an HTML template to manage a [hidden] element located in a different template using Angular 2

Unlocking the potential of GraphQL: Harnessing the power of sibling resolvers to access output from another

Steps for checking if the specified row has been accurately filled out in a loop

I'm facing a challenge with retrieving the controller's scope in my Angular directive

Utilize JavaScript to seamlessly play a Spotify track within the Spotify client without disrupting your current

passing parameters via routes

Concealing an Automatically Updated Section when Devoid of Content -- Ruby on Rails Version 4

Confirm that the input into the text box consists of three-digit numbers separated by commas

React Native Issue: Missing propType for native property RCTView.maxHeight