Given a collection of intervals, merge all overlapping intervals

problemsolving
Published

January 2, 2024

Merge Overlapping Intervals in JavaScript: A Step-by-Step Guide

Merging overlapping intervals is a classic problem in computer science with applications in various fields, from scheduling and resource allocation to data analysis. This post will walk you through solving this problem efficiently in JavaScript. We’ll cover the logic, provide clear code examples, and discuss the time and space complexity.

Understanding the Problem

The problem statement is simple: given a collection of intervals, where each interval is represented as an array [start, end], merge any overlapping intervals into a single, consolidated interval.

Example:

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Notice how [1,3] and [2,6] overlap and are merged into [1,6].

The Algorithm

The most efficient approach to solving this problem uses sorting. Here’s a breakdown of the algorithm:

  1. Sort the intervals: Sort the intervals based on their start times. This is important for efficiently identifying overlaps.

  2. Iterate and Merge: Iterate through the sorted intervals. For each interval, compare it to the last merged interval. If they overlap, merge them. If not, add the current interval to the merged intervals list.

  3. Define Overlap: Two intervals [a, b] and [c, d] overlap if a <= d and c <= b.

JavaScript Implementation

Here’s a JavaScript function that implements the algorithm:

function mergeIntervals(intervals) {
  // 1. Sort the intervals by start time
  intervals.sort((a, b) => a[0] - b[0]);

  const mergedIntervals = [];
  let currentInterval = intervals[0];

  for (let i = 1; i < intervals.length; i++) {
    const nextInterval = intervals[i];

    // 2. Check for overlap
    if (currentInterval[1] >= nextInterval[0]) {
      // Merge intervals
      currentInterval[1] = Math.max(currentInterval[1], nextInterval[1]);
    } else {
      // No overlap, add currentInterval to mergedIntervals and update currentInterval
      mergedIntervals.push(currentInterval);
      currentInterval = nextInterval;
    }
  }

  // Add the last interval
  mergedIntervals.push(currentInterval);

  return mergedIntervals;
}


// Example usage:
const intervals = [[1,3],[2,6],[8,10],[15,18]];
const merged = mergeIntervals(intervals);
console.log(merged); // Output: [[1, 6], [8, 10], [15, 18]]


const intervals2 = [[1,4],[4,5]];
const merged2 = mergeIntervals(intervals2);
console.log(merged2); // Output: [[1,5]]

const intervals3 = [[1,4],[0,4]];
const merged3 = mergeIntervals(intervals3);
console.log(merged3); // Output: [[0,4]]

Time and Space Complexity

  • Time Complexity: O(n log n), dominated by the sorting step.
  • Space Complexity: O(n) in the worst case (no overlaps), where n is the number of intervals. In the best case (all intervals overlap), the space complexity is O(1).

This approach provides an efficient and clear solution to the merging overlapping intervals problem in JavaScript. The code is well-commented and easy to understand, making it a great resource for learning about algorithm design and implementation.