Interval Problems

Interval problems involve ranges [start, end] and queries about overlaps, merges, and optimal selections. Sorting by start time (or end time, depending on the problem) is almost always the first step — it transforms a 2D problem into a linear sweep.

Overlap Detection

Two intervals [a, b] and [c, d] overlap if and only if a < d AND c < b (using strict inequalities for open intervals, ≤ for closed).

They do NOT overlap if b ≤ c or d ≤ a (one ends before the other starts).

// Check if two intervals overlap
function overlaps(a, b) {
  // [a[0], a[1]) and [b[0], b[1]) overlap iff:
  return a[0] < b[1] && b[0] < a[1];
}

console.log(overlaps([1, 3], [2, 4]));  // true   (overlap at [2,3))
console.log(overlaps([1, 3], [3, 5]));  // false  (touch but don't overlap)
console.log(overlaps([1, 5], [2, 3]));  // true   (one contains the other)

Merge Overlapping Intervals

Given an array of intervals, merge all overlapping intervals.

Algorithm:

Sort by start time
Walk through: if current interval overlaps the last merged interval, extend it
Otherwise, start a new interval in the result

// Merge Intervals — O(n log n) time
function merge(intervals) {
  if (intervals.length <= 1) return intervals;

  intervals.sort((a, b) => a[0] - b[0]);  // sort by start time

  const merged = [intervals[0]];

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

    if (curr[0] <= last[1]) {
      // Overlap: extend the last merged interval
      last[1] = Math.max(last[1], curr[1]);
    } else {
      // No overlap: add new interval
      merged.push([...curr]);
    }
  }

  return merged;
}

console.log(merge([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]

console.log(merge([[1,4],[4,5]]));
// [[1,5]] — touching intervals merge

Note

After sorting by start time, you only need to compare each interval with the **last** interval in the result. You never need to look further back — if it didn't overlap the last one, it won't overlap any earlier ones (because earlier ones end before the last one does).

Insert Interval into Sorted List

Given a sorted, non-overlapping list of intervals and a new interval to insert, merge and return the resulting sorted list.

Three phases: copy everything that ends before the new interval starts, merge everything that overlaps the new interval, then copy the rest.

// Insert Interval — O(n) time
function insert(intervals, newInterval) {
  const result = [];
  let i = 0;
  const n = intervals.length;

  // Phase 1: add all intervals that end before newInterval starts
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Phase 2: merge all overlapping intervals into newInterval
  while (i < n && 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);

  // Phase 3: add remaining intervals
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

console.log(insert([[1,3],[6,9]], [2,5]));
// [[1,5],[6,9]]

console.log(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]));
// [[1,2],[3,10],[12,16]]

Meeting Rooms I — Any Conflict?

Can a person attend all meetings (no two overlap)? Sort by start time, then check if any consecutive pair overlaps.

// Meeting Rooms I — O(n log n) time
function canAttendMeetings(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  for (let i = 1; i < intervals.length; i++) {
    // If current meeting starts before previous one ends → conflict
    if (intervals[i][0] < intervals[i - 1][1]) {
      return false;
    }
  }

  return true;
}

console.log(canAttendMeetings([[0,30],[5,10],[15,20]])); // false (0-30 conflicts with 5-10)
console.log(canAttendMeetings([[7,10],[2,4]]));           // true

Meeting Rooms II — Minimum Conference Rooms

How many conference rooms are needed to hold all meetings simultaneously?

Key insight: The minimum number of rooms equals the maximum number of concurrent meetings at any point in time.

Approach 1 — Sorted events: Separate start and end times. Sort both. Walk through:

When a meeting starts, increment active meetings
When a meeting ends, decrement active meetings
Track the maximum

Approach 2 — Min-heap: Sort by start time. Maintain a min-heap of end times for active meetings. If the earliest-ending meeting finishes before the current one starts, reuse that room. Otherwise, allocate a new room.

// Meeting Rooms II — Approach 1: sorted events O(n log n)
function minMeetingRoomsEvents(intervals) {
  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, endIdx = 0;

  for (let i = 0; i < intervals.length; i++) {
    if (starts[i] < ends[endIdx]) {
      rooms++;       // need a new room
    } else {
      endIdx++;      // reuse a room (a meeting just ended)
    }
  }

  return rooms;
}

// Meeting Rooms II — Approach 2: min-heap simulation O(n log n)
// (Using a sorted array to simulate heap for clarity)
function minMeetingRooms(intervals) {
  if (!intervals.length) return 0;
  intervals.sort((a, b) => a[0] - b[0]);

  // Min-heap of end times (simulated with sorted array for clarity)
  const heap = [];

  for (const [start, end] of intervals) {
    // If the earliest-ending meeting finishes before current one starts, reuse it
    if (heap.length > 0 && heap[0] <= start) {
      heap.shift();  // pop earliest end
    }

    // Add current meeting's end time and re-sort (simulate heap insert)
    heap.push(end);
    heap.sort((a, b) => a - b);
  }

  return heap.length;  // rooms in use = size of heap
}

console.log(minMeetingRoomsEvents([[0,30],[5,10],[15,20]])); // 2
console.log(minMeetingRooms([[0,30],[5,10],[15,20]]));        // 2
console.log(minMeetingRooms([[7,10],[2,4]]));                  // 1

Tip

The sorted events approach (Approach 1) is the most elegant. It works because when a start event occurs at the same time as an end event, the meeting that ended "makes room" for the starting one — so we process the end first (strict less-than check: `starts[i] < ends[endIdx]`).

Non-Overlapping Intervals — Minimum Removals

Remove the minimum number of intervals so the rest don't overlap. Equivalent to: keep the maximum number of non-overlapping intervals, then subtract from total.

Greedy: Sort by end time, keep intervals that start at or after the last kept end.

// Non-overlapping Intervals — O(n log n)
function eraseOverlapIntervals(intervals) {
  if (!intervals.length) return 0;

  intervals.sort((a, b) => a[1] - b[1]);  // sort by END time

  let keep = 1;
  let lastEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= lastEnd) {
      keep++;
      lastEnd = intervals[i][1];
    }
    // else: overlaps — skip (remove) this interval
  }

  return intervals.length - keep;
}

console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1  (remove [1,3])
console.log(eraseOverlapIntervals([[1,2],[1,2],[1,2]]));        // 2
console.log(eraseOverlapIntervals([[1,2],[2,3]]));              // 0  (no overlap)

Interval List Intersections

Given two sorted lists of non-overlapping intervals, find all intersections. Use a two-pointer approach — advance the pointer whose interval ends first.

// Interval List Intersections — O(m + n) time
function intervalIntersection(firstList, secondList) {
  const result = [];
  let i = 0, j = 0;

  while (i < firstList.length && j < secondList.length) {
    const [a0, a1] = firstList[i];
    const [b0, b1] = secondList[j];

    // Intersection is [max(starts), min(ends)] if max(starts) <= min(ends)
    const lo = Math.max(a0, b0);
    const hi = Math.min(a1, b1);

    if (lo <= hi) result.push([lo, hi]);

    // Advance the pointer for the interval that ends first
    if (a1 < b1) i++;
    else j++;
  }

  return result;
}

const A = [[0,2],[5,10],[13,23],[24,25]];
const B = [[1,5],[8,12],[15,24],[25,26]];
console.log(intervalIntersection(A, B));
// [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Employee Free Time

Given schedules (sorted lists of intervals) for each employee, find all time slots when ALL employees are free (gaps in the union of all intervals).

Approach: Flatten all intervals, sort by start time, merge, then find gaps.

// Employee Free Time — O(n log n) where n = total intervals
function employeeFreeTime(schedules) {
  // Flatten all intervals
  const all = schedules.flat();
  all.sort((a, b) => a[0] - b[0]);

  const freeTimes = [];
  let end = all[0][1];  // track the end of the current "busy block"

  for (let i = 1; i < all.length; i++) {
    if (all[i][0] > end) {
      // Gap between end of last busy block and start of this one
      freeTimes.push([end, all[i][0]]);
    }
    end = Math.max(end, all[i][1]);
  }

  return freeTimes;
}

// Employee 1: [1,3],[6,7]  Employee 2: [2,4]  Employee 3: [2,5],[9,12]
const schedules = [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]];
console.log(employeeFreeTime(schedules));
// [[5,6],[7,9]] — everyone is free 5-6 and 7-9

Interval Problems Decision Guide

Problem	Sort By	Technique	Time
Merge intervals	Start time	Extend last interval on overlap	O(n log n)
Insert interval	Already sorted	Three-phase linear scan	O(n)
Meeting Rooms I	Start time	Check adjacent pairs	O(n log n)
Meeting Rooms II	Start/end separately	Two-pointer or heap	O(n log n)
Non-overlapping intervals	End time	Greedy keep earliest end	O(n log n)
Interval intersections	Already sorted	Two-pointer advance	O(m+n)
Employee free time	Start time	Merge + find gaps	O(n log n)

Warning

Sorting by end time vs start time changes the greedy choice. For "maximum non-overlapping intervals" and "minimum removals," sort by END time — this leaves the most room for future intervals. For "merge" and "detect any overlap," sort by START time.

Sorting is almost always the first step — determine whether start or end time is the key
After sorting, most interval problems reduce to a linear scan
The "last end" variable tracks the frontier of the current contiguous region
Meeting Rooms II: max concurrent = rooms needed = peak of a sweep line
For intersections of two sorted lists, two-pointer runs in O(m+n) without any extra sorting