Merge Intervals: Simplifying Overlapping Ranges

The "Merge Intervals" problem is a fundamental challenge in array manipulation, involving the combination of overlapping intervals into a minimal set of non-overlapping intervals.

Problem Statement

Given an array of intervals where each interval is represented as a pair [start, end], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example

• Input: Intervals [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, they are merged into [1,6].

Solution Approach

function merge(intervals) {
  if (!intervals.length) return [];

  // Sort the intervals based on the start times
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const lastMerged = merged[merged.length - 1];
    const current = intervals[i];

    if (current[0] <= lastMerged[1]) {
      // Overlapping intervals, merge them
      lastMerged[1] = Math.max(lastMerged[1], current[1]);
    } else {
      // Non-overlapping interval, add to the result
      merged.push(current);
    }
  }

  return merged;
}

Breaking Down the Solution

• Sort Intervals: First, sort the intervals based on their starting points.
• Initialize Merged List: Start with the first interval in the merged list.
• Iterate and Merge: Go through each interval and merge it with the last interval in the merged list if they overlap. If they don't overlap, add the interval to the merged list.
• Return Merged Intervals: The merged list now contains the minimal set of non-overlapping intervals.

Conclusion

The Merge Intervals problem is a classic example of interval manipulation and is critical in many applications, such as calendar events, scheduling algorithms, and time-based data analysis. It emphasizes the importance of sorting and efficient merging in array processing.