Intervals Explained

Interval problems deal with ranges like meeting times, task schedules, or subarray spans. The recurring trick is to sort intervals by start time, then sweep over them merging or resolving overlaps. This pattern converts O(n²) pairwise checks into a single O(n) pass and shows up in Amazon, Google, Meta, and Microsoft loops.

The Two Overlap Rules

For inclusive intervals [start, end], two intervals overlap when:

overlap([a,b], [c,d]) = a <= d && c <= b
// Dates/numbers:  [1,3] and [3,5] DO overlap at 3
// Half-open [1,3) and [3,5): DO NOT overlap

Scheduling problems often use half-open intervals (a meeting ends before the next starts), so confirm the intent with the interviewer before writing comparison code.

Merge Intervals

Sort by start, then walk through. If the next interval overlaps the current merged one, extend the end; otherwise flush the current interval and start a new one.

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const res: number[][] = [];
  for (const [s, e] of intervals) {
    const last = res[res.length - 1];
    if (res.length && s <= last[1]) {
      last[1] = Math.max(last[1], e);       // extend overlap
    } else {
      res.push([s, e]);                      // no overlap, new bucket
    }
  }
  return res;
}
// Time: O(n log n), Space: O(n)

graph TD
    A["[1,3]"] --> B["[2,6]"]
    B --> C["[8,10]"]
    C --> D["[15,18]"]
    style A fill:#D4EDDA,stroke:#28A745
    style B fill:#D4EDDA,stroke:#28A745
    style C fill:#FFF3CD,stroke:#FFC107
    style D fill:#FFF3CD,stroke:#FFC107

[1,3] and [2,6] overlap and merge into [1,6]; [8,10] and [15,18] stay separate.

Insert Interval

Insert a new interval into an already-sorted list without re-sorting. Walk the list, keeping everything that ends before the new interval starts, merging everything it overlaps, then appending the rest:

function insert(intervals: number[][], newI: number[]): number[][] {
  const res: number[][] = [];
  let [ns, ne] = newI;
  let i = 0;
  while (i < intervals.length && intervals[i][1] < ns) {
    res.push(intervals[i]); i++;              // before overlap
  }
  while (i < intervals.length && intervals[i][0] <= ne) {
    ns = Math.min(ns, intervals[i][0]);
    ne = Math.max(ne, intervals[i][1]);
    i++;                                      // absorb overlaps
  }
  res.push([ns, ne]);                          // the merged interval
  while (i < intervals.length) { res.push(intervals[i]); i++; }
  return res;
}
// Time: O(n), Space: O(n)

Meeting Rooms (Can One Person Attend All?)

Sort by start and check no two neighbors overlap.

function canAttendAll(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;
}

Meeting Rooms II (Minimum Rooms)

Count the maximum simultaneous overlaps. With all intervals sorted, use a min-heap of end times : when a new meeting starts, pop ended meetings, and the heap size at any point is the rooms in use.

function minRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  const ends: number[] = [];                          // min-heap of end times
  const push = (v: number) => { ends.push(v); ends.sort((a, b) => a - b); };
  const pop = () => ends.shift();
  for (const [s, e] of intervals) {
    if (ends.length && ends[0] <= s) pop();           // room freed
    push(e);
  }
  return ends.length;
}
// Time: O(n log n)

An alternative many candidates prefer: split into start-time and end-time lists, sort both, and sweep with two pointers counting the active meetings.

Non-overlapping Intervals (Greedy)

Find how many intervals to remove so the rest never overlap. The greedy rule: keep the interval that ends earliest, because it leaves the most room for the rest.

function eraseOverlap(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);               // sort by END
  let end = -Infinity, kept = 0;
  for (const [s, e] of intervals) {
    if (s >= end) { kept++; end = e; }                 // compatible
  }
  return intervals.length - kept;                       // removals
}

Sorting by end time instead of start time is the crux and a classic interview differentiator.

Interval List Intersections

Given two sorted lists of intervals, walk both with two pointers. The intersection is [max(startA, startB), min(endA, endB)] if valid, then advance the list whose interval ends first.

Common Mistakes

• Sorting by end time when the problem needs start time, and vice versa. Merging sorts by start; greedy non-overlap sorts by end.
• Getting the inclusive overlap check wrong : a <= d && c <= b, not strict bounds.
• Forgetting that [1,3] and [3,5] overlap for inclusive intervals.
• Mutating inputs before a second pass; clone intervals when you need the original order.
• Not handling empty input or single-interval lists.

Frequently Asked Questions

Related Tutorials

• Greedy Algorithms : the decision rule behind non-overlapping intervals.
• Heaps : the end-time heap in Meeting Rooms II.
• Sorting Algorithms : the sort that drives every sweep.
• Interval practice problems : many interval questions are tagged under sorting.