Merge Intervals Pattern

When to use Merge Intervals

• The input is a list of pairs (start, end), and the answer depends on how they overlap.
• You need to merge overlapping intervals, insert a new interval, or remove the minimum number of intervals to make the rest disjoint.
• You need to find conflict-free meeting room assignments or maximum room usage.
• You need to compute the union, intersection, or symmetric difference of two interval lists.
• You can sort the input by start time as a one-time preprocessing step.

Template

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    const current = intervals[i];
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push(current);
    }
  }
  return merged;
}

Common mistakes

• Sorting by end time when the algorithm requires start time (or vice versa for the greedy non-overlapping variant).
• Using strict `<` instead of `<=` when checking overlap, which fails for intervals that touch at a single point if the problem treats that as overlapping.
• Mutating the input intervals in place and then returning the wrong reference (the original head is no longer the merged head).
• Building a new array for every merge step in O(n^2) instead of mutating the last element of the result list.
• Forgetting to handle the empty input case, which throws when the algorithm reads `intervals[0]` to seed the loop.