08. Merge Intervals

TL;DR

After sorting intervals by start time (and breaking ties by end if needed), a single left-to-right scan merges overlapping pieces into a convex chain of disjoint blocks. The same sorted skeleton supports inserting one new interval, dropping the fewest meetings to remove overlap (greedy by end), and counting concurrent meetings with a min-heap of end times (next free room is whoever finishes earliest).

Recognition Cues

Phrases: “merge overlapping intervals,” “insert interval into sorted set,” “minimum rooms / maximum concurrent,” “remove minimum intervals to be non-overlapping,” “intersection of two interval lists,” “skyline” (sweep with heap).
Inputs: [][]int as [start, end], or meeting start/end times; may be unsorted.
Outputs: merged list, a count, or a boolean schedule fit.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Loading diagram…

Mental Model

Sorting by start means the only interval that can threaten the current merged block is the next one in order; if next.start <= current.end, they share time — extend current.end to max(ends); else push current and start a new block.
Meeting rooms II: chronologically, each start needs a room; a min-heap of end times tells you the earliest room that frees; if start < heap.min, you need a new room.
Non-overlapping removal: process by ending soonest (greedy) to keep room for future intervals — sort by end, count compatible chain.

Generic Recipe

Sort by interval[0]; optional secondary sort by interval[1].
Merge: keep current; for each next, overlap ⇔ next[0] <= current[1]; merge or append.
Insert: merge the one new interval with the already merged or scan linear in sorted order in one pass.
Minimum removal (max non-overlapping): sort by end; greedily take intervals whose start is after the last chosen end.
Meeting rooms: sort by start; min-heap of end times; pushpop logic per start.

Complexity

Sort: O(n log n) time, O(1) to O(n) extra space depending on sort.
Merge pass: O(n) after sort.
Heap for rooms: O(n log n) time, O(n) space for the heap.

Generic Code Template

Go

package main

import (
	"container/heap"
	"sort"
)

func mergeIntervals(intervals [][]int) [][]int {
	if len(intervals) == 0 {
		return nil
	}
	sort.Slice(intervals, func(left, right int) bool {
		if intervals[left][0] == intervals[right][0] {
			return intervals[left][1] < intervals[right][1]
		}
		return intervals[left][0] < intervals[right][0]
	})
	merged := [][]int{intervals[0]}
	for index := 1; index < len(intervals); index++ {
		lastIndex := len(merged) - 1
		if intervals[index][0] <= merged[lastIndex][1] {
			if intervals[index][1] > merged[lastIndex][1] {
				merged[lastIndex][1] = intervals[index][1]
			}
		} else {
			merged = append(merged, []int{intervals[index][0], intervals[index][1]})
		}
	}
	return merged
}

// minEndHeap for meeting room end times.
type minEndHeap []int

func (heapData minEndHeap) Len() int            { return len(heapData) }
func (heapData minEndHeap) Less(a, b int) bool { return heapData[a] < heapData[b] }
func (heapData minEndHeap) Swap(a, b int)      { heapData[a], heapData[b] = heapData[b], heapData[a] }
func (heapData *minEndHeap) Push(value any)   { *heapData = append(*heapData, value.(int)) }
func (heapData *minEndHeap) Pop() any {
	old := *heapData
	last := len(old) - 1
	v := old[last]
	*heapData = old[:last]
	return v
}

func minMeetingRooms(meetings [][]int) int {
	if len(meetings) == 0 {
		return 0
	}
	sort.Slice(meetings, func(a, b int) bool { return meetings[a][0] < meetings[b][0] })
	roomHeap := &minEndHeap{}
	heap.Init(roomHeap)
	for _, meeting := range meetings {
		start := meeting[0]
		end := meeting[1]
		if roomHeap.Len() > 0 && start >= (*roomHeap)[0] {
			heap.Pop(roomHeap)
		}
		heap.Push(roomHeap, end)
	}
	return roomHeap.Len()
}

func main() {
	_ = mergeIntervals([][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}})
	_ = minMeetingRooms([][]int{{0, 30}, {5, 10}, {15, 20}})
}

JavaScript

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  const sorted = [...intervals].sort((left, right) => {
    if (left[0] !== right[0]) return left[0] - right[0];
    return left[1] - right[1];
  });
  const merged = [sorted[0].slice()];
  for (let index = 1; index < sorted.length; index++) {
    const last = merged[merged.length - 1];
    const next = sorted[index];
    if (next[0] <= last[1]) {
      last[1] = Math.max(last[1], next[1]);
    } else {
      merged.push(next.slice());
    }
  }
  return merged;
}

class MinHeap {
  constructor() {
    this.data = [];
  }
  size() {
    return this.data.length;
  }
  peek() {
    return this.data[0];
  }
  push(value) {
    this.data.push(value);
    this.#bubbleUp(this.data.length - 1);
  }
  pop() {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.#bubbleDown(0);
    }
    return top;
  }
  #parent(index) {
    return Math.floor((index - 1) / 2);
  }
  #bubbleUp(index) {
    while (index > 0) {
      const parentIndex = this.#parent(index);
      if (this.data[parentIndex] <= this.data[index]) break;
      [this.data[parentIndex], this.data[index]] = [
        this.data[index],
        this.data[parentIndex],
      ];
      index = parentIndex;
    }
  }
  #bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      let smallest = index;
      if (left < length && this.data[left] < this.data[smallest]) {
        smallest = left;
      }
      if (right < length && this.data[right] < this.data[smallest]) {
        smallest = right;
      }
      if (smallest === index) break;
      [this.data[index], this.data[smallest]] = [
        this.data[smallest],
        this.data[index],
      ];
      index = smallest;
    }
  }
}

function minMeetingRooms(meetings) {
  if (meetings.length === 0) return 0;
  const sorted = [...meetings].sort((a, b) => a[0] - b[0]);
  const endHeap = new MinHeap();
  for (const meeting of sorted) {
    const start = meeting[0];
    const end = meeting[1];
    if (endHeap.size() > 0 && start >= endHeap.peek()) {
      endHeap.pop();
    }
    endHeap.push(end);
  }
  return endHeap.size();
}

Variants

Insert interval: merge into existing sorted merged list in one scan or binary-search position then merge neighbors.
Non-overlapping removal: 435 — greedy by ascending end.
Meeting rooms II: heap of end times; 252 is feasibility with one room (check end of previous ≤ start of next after sort).
Interval list intersections: two pointers on two sorted lists, advancing whoever ends first.
Min interval to include query: sort + heap / offline queries (1851).

Representative Problems

56. Merge Intervals — sort by start, sweep merge
57. Insert Interval — merge after insertion point
435. Non-overlapping Intervals — greedy by end
253. Meeting Rooms II — min-heap of end times
252. Meeting Rooms — single-room feasibility

Anti-patterns

Merging without sorting first — overlaps across distant intervals are missed.
Confusing <= vs < on boundary-touching intervals — follow the problem: touching intervals [1,5][5,8] often merge to [1,8].
Using meeting-rooms heap when only one counter and greedy end-time suffice for “max non-overlap.”
Returning merged intervals sharing underlying slices — copy when callers mutate.

On this page