Merge Intervals

Overview

Merge Intervals is a technique for combining overlapping or adjacent intervals into consolidated ranges. Given a collection of intervals, you merge those that overlap or are adjacent, resulting in a simplified set of non-overlapping intervals.

The key insight: sort intervals by start time, then iterate through them. If current interval overlaps with the last merged interval, merge them. Otherwise, add current interval as a new merged interval.

Merge intervals is particularly useful for:

• Combining overlapping time ranges
• Scheduling problems
• Range consolidation
• Meeting room problems
• Interval insertion
• Non-overlapping intervals

Pattern 1: Merge Intervals (Basic)

Merge all overlapping intervals.

function merge(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];
  
  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);
  
  const merged: number[][] = [intervals[0]];
  
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];
    
    // If current overlaps with last, merge them
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      // No overlap, add as new interval
      merged.push(current);
    }
  }
  
  return merged;
}

Time: O(n log n), Space: O(n)

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

Pattern 2: Insert Interval

Insert new interval and merge if necessary.

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let i = 0;
  
  // Add all intervals before newInterval
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }
  
  // Merge overlapping intervals
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  
  result.push(newInterval);
  
  // Add remaining intervals
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  
  return result;
}

Time: O(n), Space: O(n)

If intervals are sorted:

function insertSorted(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let inserted = false;
  
  for (const interval of intervals) {
    if (interval[1] < newInterval[0]) {
      result.push(interval);
    } else if (interval[0] > newInterval[1]) {
      if (!inserted) {
        result.push(newInterval);
        inserted = true;
      }
      result.push(interval);
    } else {
      // Merge overlapping intervals
      newInterval[0] = Math.min(newInterval[0], interval[0]);
      newInterval[1] = Math.max(newInterval[1], interval[1]);
    }
  }
  
  if (!inserted) {
    result.push(newInterval);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 3: Non-Overlapping Intervals

Remove minimum intervals to make rest non-overlapping.

function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length === 0) return 0;
  
  // Sort by end time
  intervals.sort((a, b) => a[1] - b[1]);
  
  let count = 0;
  let end = intervals[0][1];
  
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < end) {
      // Overlapping, remove this interval
      count++;
    } else {
      // Non-overlapping, update end
      end = intervals[i][1];
    }
  }
  
  return count;
}

Time: O(n log n), Space: O(1)

Greedy strategy: Always keep interval with earliest end time when overlapping.

Pattern 4: Meeting Rooms

Check if person can attend all meetings.

function canAttendMeetings(intervals: number[][]): boolean {
  intervals.sort((a, b) => a[0] - b[0]);
  
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) {
      return false;
    }
  }
  
  return true;
}

Time: O(n log n), Space: O(1)

Pattern 5: Meeting Rooms II

Find minimum rooms needed for all meetings.

function minMeetingRooms(intervals: number[][]): number {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
  
  let rooms = 0;
  let endIndex = 0;
  
  for (let i = 0; i < starts.length; i++) {
    if (starts[i] < ends[endIndex]) {
      // Need new room
      rooms++;
    } else {
      // Reuse room, move to next end time
      endIndex++;
    }
  }
  
  return rooms;
}

Time: O(n log n), Space: O(n)

Using priority queue:

function minMeetingRoomsPQ(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  
  const heap: number[] = []; // Min heap of end times
  
  for (const [start, end] of intervals) {
    if (heap.length > 0 && heap[0] <= start) {
      // Reuse room
      heap.shift(); // Remove earliest end
    }
    heap.push(end);
    heap.sort((a, b) => a - b); // Maintain min heap
  }
  
  return heap.length;
}

Time: O(n log n), Space: O(n)

Pattern 6: Interval List Intersections

Find intersection of two interval lists.

function intervalIntersection(
  firstList: number[][],
  secondList: number[][]
): number[][] {
  const result: number[][] = [];
  let i = 0, j = 0;
  
  while (i < firstList.length && j < secondList.length) {
    const [start1, end1] = firstList[i];
    const [start2, end2] = secondList[j];
    
    // Find intersection
    const start = Math.max(start1, start2);
    const end = Math.min(end1, end2);
    
    if (start <= end) {
      result.push([start, end]);
    }
    
    // Move pointer with smaller end time
    if (end1 < end2) {
      i++;
    } else {
      j++;
    }
  }
  
  return result;
}

Time: O(n + m), Space: O(n + m)

Pattern 7: Partition Labels

Partition string into as many parts as possible with unique characters.

function partitionLabels(s: string): number[] {
  const lastIndex = new Map<string, number>();
  
  // Record last occurrence of each character
  for (let i = 0; i < s.length; i++) {
    lastIndex.set(s[i], i);
  }
  
  const result: number[] = [];
  let start = 0;
  let end = 0;
  
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, lastIndex.get(s[i])!);
    
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }
  
  return result;
}

Time: O(n), Space: O(1) for alphabet size

Explanation: Each partition is an interval [start, end] where all characters in range appear only in that range.

Pattern 8: Employee Free Time

Find common free time for all employees.

function employeeFreeTime(schedule: number[][][]): number[][] {
  // Flatten all intervals
  const intervals: number[][] = [];
  for (const empSchedule of schedule) {
    intervals.push(...empSchedule);
  }
  
  // Sort and merge
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = merge(intervals);
  
  // Find gaps between merged intervals
  const freeTime: number[][] = [];
  for (let i = 1; i < merged.length; i++) {
    freeTime.push([merged[i - 1][1], merged[i][0]]);
  }
  
  return freeTime;
}

Time: O(n log n), Space: O(n)

Pattern 9: Remove Covered Intervals

Remove intervals covered by another interval.

function removeCoveredIntervals(intervals: number[][]): number {
  // Sort by start (ascending), then by end (descending)
  intervals.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0];
    return b[1] - a[1];
  });
  
  let count = 0;
  let end = -1;
  
  for (const [start, currEnd] of intervals) {
    if (currEnd > end) {
      // Not covered
      count++;
      end = currEnd;
    }
    // else: covered by previous interval
  }
  
  return intervals.length - count;
}

Time: O(n log n), Space: O(1)

Explanation: Sort ensures if interval A covers B, A comes before B. Track maximum end seen.

Pattern 10: Merge Intervals with Custom Comparator

Merge intervals based on custom overlap condition.

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

// Example: Merge if gap <= threshold
const mergeWithGap = (intervals: number[][], gap: number): number[][] => {
  return mergeCustom(intervals, (a, b) => b[0] - a[1] <= gap);
};

Time: O(n log n), Space: O(n)

Pattern 11: Maximum Number of Non-Overlapping Intervals

Find maximum number of non-overlapping intervals.

function maxNonOverlappingIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  
  let count = 0;
  let end = -Infinity;
  
  for (const [start, currEnd] of intervals) {
    if (start >= end) {
      count++;
      end = currEnd;
    }
  }
  
  return count;
}

Time: O(n log n), Space: O(1)

Greedy: Always pick interval with earliest end time.

Pattern 12: Interval Scheduling with Weights

Maximize total weight of non-overlapping intervals.

function maxWeightIntervals(intervals: number[][]): number {
  const n = intervals.length;
  intervals.sort((a, b) => a[1] - b[1]);
  
  // DP: dp[i] = max weight using intervals[0..i]
  const dp = new Array(n).fill(0);
  dp[0] = intervals[0][2]; // Assuming weight is third element
  
  for (let i = 1; i < n; i++) {
    const [start, end, weight] = intervals[i];
    
    // Option 1: Don't include current interval
    dp[i] = dp[i - 1];
    
    // Option 2: Include current interval
    // Find last non-overlapping interval
    let lastNonOverlap = -1;
    for (let j = i - 1; j >= 0; j--) {
      if (intervals[j][1] <= start) {
        lastNonOverlap = j;
        break;
      }
    }
    
    const weightWithCurrent = weight + (lastNonOverlap >= 0 ? dp[lastNonOverlap] : 0);
    dp[i] = Math.max(dp[i], weightWithCurrent);
  }
  
  return dp[n - 1];
}

Time: O(n²), Space: O(n)

Optimized with binary search:

function maxWeightIntervalsOptimized(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  
  const dp = new Array(intervals.length).fill(0);
  dp[0] = intervals[0][2];
  
  for (let i = 1; i < intervals.length; i++) {
    const [start, end, weight] = intervals[i];
    
    // Binary search for last non-overlapping interval
    let left = 0, right = i - 1;
    let lastNonOverlap = -1;
    
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (intervals[mid][1] <= start) {
        lastNonOverlap = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    dp[i] = Math.max(
      dp[i - 1],
      weight + (lastNonOverlap >= 0 ? dp[lastNonOverlap] : 0)
    );
  }
  
  return dp[intervals.length - 1];
}

Time: O(n log n), Space: O(n)

When to Use Merge Intervals

Use merge intervals when:

• Problem involves overlapping ranges
• Need to consolidate intervals
• Scheduling problems (meetings, events)
• Time range operations
• Non-overlapping intervals required
• Interval intersection problems
• Gap detection between intervals

Key steps:

1. Sort intervals by start time
2. Iterate and merge overlapping intervals
3. Use greedy approach for optimization

Template (Basic Merge)

function mergeIntervalsTemplate(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];
  
  intervals.sort((a, b) => a[0] - b[0]);
  
  const merged: number[][] = [intervals[0]];
  
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];
    
    if (current[0] <= last[1]) {
      // Overlapping: merge
      last[1] = Math.max(last[1], current[1]);
    } else {
      // Non-overlapping: add new
      merged.push(current);
    }
  }
  
  return merged;
}

Template (Greedy Selection)

function greedyIntervalsTemplate(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]); // Sort by end time
  
  let count = 0;
  let end = -Infinity;
  
  for (const [start, currEnd] of intervals) {
    if (start >= end) {
      count++;
      end = currEnd;
    }
  }
  
  return count;
}

Time and Space Complexity Summary

• Basic merge: O(n log n) time, O(n) space
• Insert interval: O(n) time, O(n) space
• Non-overlapping: O(n log n) time, O(1) space
• Meeting rooms: O(n log n) time, O(n) space
• Interval intersection: O(n + m) time, O(n + m) space
• Weighted intervals: O(n log n) time, O(n) space

Practice Tips

1. Sort first - Usually by start time or end time
2. Greedy strategy - Pick earliest end time for non-overlapping
3. Overlap check - a[0] <= b[1] && b[0] <= a[1]
4. Two pointers - For interval intersection
5. Binary search - Optimize weighted interval problems

Common Mistakes

1. Not sorting - Forgetting to sort intervals first
2. Wrong comparator - Sorting by wrong field
3. Overlap logic - Incorrect overlap detection
4. Boundary cases - Empty intervals, single interval
5. Merge condition - Not handling adjacent intervals correctly

Related Concepts

• Sorting - Essential first step
• Greedy Algorithm - For optimization problems
• Two Pointers - For interval intersection
• Dynamic Programming - For weighted intervals

Merge intervals is essential for range and scheduling problems. Master these patterns, and you'll efficiently solve interval-related problems in coding interviews.