The Anatomy of Merging: Scenarios, Steps, and Solution Complexity

A Closer Look at Merge Scenarios

Before diving further into the code, let's acquaint ourselves with the various situations where merging becomes necessary. For a detailed understanding, you can explore all possible merging scenarios here.

Initialize Result Storage

Once our ranges are sorted, we start with an empty result array to store our final merged intervals.

Iterating and Merging: A Walkthrough

After sorting by the starting time, we have our array looking like [[1, 4], [2, 5], [7, 10], [12, 16]]. Now comes the fun part — iterating through these intervals and deciding when to merge.

Determining Overlap via Code

We'll iterate through our sorted ranges. To do this efficiently, we maintain a variable called last, which tracks the last interval we've encountered. As we go through each range r in ranges, we'll need to decide whether to extend last or append a new range to our result. Here's how:

1. Checking for Overlap: If the start time of r (r[0]) is less than or equal to the end time of last (last[1]), we have an overlap.
2. Extending the Interval: In the case of an overlap, we update last[1] to be the maximum between r[1] and last[1]. This ensures that last covers the entirety of the overlapping period.

Identifying Clear Separations

If there is no overlap — i.e., a "clear separation" exists — we simply append the new range to our result. A clear separation is evident when last[1] is less than r[0]. In such a case, r starts strictly after last ends, and hence no merge is necessary.

xxxxxxxxxx

const ranges = [

  [1, 4],

  [2, 5],

];

​

const result = [];

let last;

ranges.forEach(function (r) {

  // compare this new range to the last one we tracked

  // if this range has a time gap before the next event, add to results

  if (!last || r[0] > last[1]) {

    last = r;

    result.push(last);

  } else if (r[1] > last[1]) {

    // otherwise if its end time is longer than the last,

    // extend the last range's end time to encompass this interval too

    last[1] = r[1];

  }

});

​

console.log(result);