Interval Problems - Complete Guide | Chinese Powered Labs

Interval problems involve working with ranges or time periods. This guide covers common patterns and algorithms for solving interval-related challenges.

Understanding Intervals #

An interval is a continuous range represented as [start, end].

const interval = [1, 5];  // Includes 1 and 5
// Represents: 1, 2, 3, 4, 5

// Common representations:
// [start, end] - Closed interval (inclusive)
// (start, end) - Open interval (exclusive)
// [start, end) - Half-open (start inclusive, end exclusive)

Merge Intervals #

Combine overlapping intervals.

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

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

  const merged = [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 interval
      merged.push(current);
    }
  }

  return merged;
}

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

console.log(mergeIntervals([[1, 4], [4, 5]]));
// [[1, 5]]

Insert Interval #

Insert new interval and merge if needed.

function insert(intervals, newInterval) {
  const result = [];
  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;
}

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]]

Non-Overlapping Intervals #

Remove minimum intervals to make rest non-overlapping.

function eraseOverlapIntervals(intervals) {
  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 current
      count++;
    } else {
      // Non-overlapping - update end
      end = intervals[i][1];
    }
  }

  return count;
}

console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]));  // 1
console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]));  // 2

Meeting Rooms #

Check if person can attend all meetings.

function canAttendMeetings(intervals) {
  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;  // Overlap found
    }
  }

  return true;
}

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

Meeting Rooms II #

Find minimum conference rooms needed.

function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;

  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 endPtr = 0;

  for (let i = 0; i < starts.length; i++) {
    if (starts[i] < ends[endPtr]) {
      // Need new room
      rooms++;
    } else {
      // Reuse room
      endPtr++;
    }
  }

  return rooms;
}

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

Using Min Heap #

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  peek() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.heap[parent] <= this.heap[index]) break;
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
    }
  }

  bubbleDown(index) {
    while (true) {
      let smallest = index;
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;

  intervals.sort((a, b) => a[0] - b[0]);

  const heap = new MinHeap();
  heap.push(intervals[0][1]);

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= heap.peek()) {
      heap.pop();
    }
    heap.push(intervals[i][1]);
  }

  return heap.size();
}

Minimum Arrows to Burst Balloons #

function findMinArrowShots(points) {
  if (points.length === 0) return 0;

  // Sort by end position
  points.sort((a, b) => a[1] - b[1]);

  let arrows = 1;
  let end = points[0][1];

  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > end) {
      // Need new arrow
      arrows++;
      end = points[i][1];
    }
  }

  return arrows;
}

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

Interval List Intersections #

function intervalIntersection(firstList, secondList) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < firstList.length && j < secondList.length) {
    const start = Math.max(firstList[i][0], secondList[j][0]);
    const end = Math.min(firstList[i][1], secondList[j][1]);

    if (start <= end) {
      result.push([start, end]);
    }

    // Move pointer with smaller end
    if (firstList[i][1] < secondList[j][1]) {
      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 #

Find common free time for all employees.

function employeeFreeTime(schedule) {
  const intervals = [];

  // Flatten all intervals
  for (const employee of schedule) {
    for (const interval of employee) {
      intervals.push(interval);
    }
  }

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

  // Merge intervals
  const merged = [intervals[0]];

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

    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      merged.push(intervals[i]);
    }
  }

  // Find gaps (free time)
  const freeTime = [];

  for (let i = 1; i < merged.length; i++) {
    freeTime.push([merged[i - 1][1], merged[i][0]]);
  }

  return freeTime;
}

const schedule = [
  [[1, 3], [4, 6]],
  [[1, 3], [9, 12]],
  [[1, 3]]
];

console.log(employeeFreeTime(schedule));
// [[6, 9]]

My Calendar #

Book intervals without conflicts.

class MyCalendar {
  constructor() {
    this.calendar = [];
  }

  book(start, end) {
    for (const [s, e] of this.calendar) {
      if (start < e && end > s) {
        return false;  // Overlap
      }
    }

    this.calendar.push([start, end]);
    return true;
  }
}

const cal = new MyCalendar();
console.log(cal.book(10, 20));  // true
console.log(cal.book(15, 25));  // false
console.log(cal.book(20, 30));  // true

Optimized with Binary Search #

class MyCalendar {
  constructor() {
    this.calendar = [];
  }

  book(start, end) {
    let left = 0;
    let right = this.calendar.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (this.calendar[mid][0] < start) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    // Check previous interval
    if (left > 0 && this.calendar[left - 1][1] > start) {
      return false;
    }

    // Check next interval
    if (left < this.calendar.length && this.calendar[left][0] < end) {
      return false;
    }

    this.calendar.splice(left, 0, [start, end]);
    return true;
  }
}

My Calendar II #

Allow at most double booking.

class MyCalendarTwo {
  constructor() {
    this.calendar = [];
    this.overlaps = [];
  }

  book(start, end) {
    // Check for triple booking
    for (const [s, e] of this.overlaps) {
      if (start < e && end > s) {
        return false;
      }
    }

    // Add new overlaps
    for (const [s, e] of this.calendar) {
      if (start < e && end > s) {
        this.overlaps.push([Math.max(start, s), Math.min(end, e)]);
      }
    }

    this.calendar.push([start, end]);
    return true;
  }
}

const cal = new MyCalendarTwo();
console.log(cal.book(10, 20));  // true
console.log(cal.book(50, 60));  // true
console.log(cal.book(10, 40));  // true (double booking 10-20)
console.log(cal.book(5, 15));   // false (would triple book 10-15)

Car Pooling #

Check if carpool capacity sufficient.

function carPooling(trips, capacity) {
  const events = [];

  for (const [passengers, from, to] of trips) {
    events.push([from, passengers]);   // Pick up
    events.push([to, -passengers]);    // Drop off
  }

  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

  let current = 0;

  for (const [location, change] of events) {
    current += change;
    if (current > capacity) {
      return false;
    }
  }

  return true;
}

console.log(carPooling([[2, 1, 5], [3, 3, 7]], 4));  // false
console.log(carPooling([[2, 1, 5], [3, 3, 7]], 5));  // true

Range Addition #

function getModifiedArray(length, updates) {
  const result = new Array(length).fill(0);

  for (const [start, end, inc] of updates) {
    result[start] += inc;
    if (end + 1 < length) {
      result[end + 1] -= inc;
    }
  }

  // Prefix sum
  for (let i = 1; i < length; i++) {
    result[i] += result[i - 1];
  }

  return result;
}

console.log(getModifiedArray(5, [[1, 3, 2], [2, 4, 3], [0, 2, -2]]));
// [-2, 0, 3, 5, 3]

Data Stream as Disjoint Intervals #

class SummaryRanges {
  constructor() {
    this.intervals = [];
  }

  addNum(val) {
    const newInterval = [val, val];
    const merged = [];
    let i = 0;

    // Add intervals before new value
    while (i < this.intervals.length && this.intervals[i][1] + 1 < val) {
      merged.push(this.intervals[i]);
      i++;
    }

    // Merge overlapping intervals
    while (i < this.intervals.length && this.intervals[i][0] - 1 <= val) {
      newInterval[0] = Math.min(newInterval[0], this.intervals[i][0]);
      newInterval[1] = Math.max(newInterval[1], this.intervals[i][1]);
      i++;
    }
    merged.push(newInterval);

    // Add remaining intervals
    while (i < this.intervals.length) {
      merged.push(this.intervals[i]);
      i++;
    }

    this.intervals = merged;
  }

  getIntervals() {
    return this.intervals;
  }
}

const sr = new SummaryRanges();
sr.addNum(1);
console.log(sr.getIntervals());  // [[1, 1]]
sr.addNum(3);
console.log(sr.getIntervals());  // [[1, 1], [3, 3]]
sr.addNum(7);
console.log(sr.getIntervals());  // [[1, 1], [3, 3], [7, 7]]
sr.addNum(2);
console.log(sr.getIntervals());  // [[1, 3], [7, 7]]
sr.addNum(6);
console.log(sr.getIntervals());  // [[1, 3], [6, 7]]

Time Complexity #

Problem	Time Complexity	Space Complexity
Merge Intervals	O(n log n)	O(n)
Insert Interval	O(n)	O(n)
Non-overlapping	O(n log n)	O(1)
Meeting Rooms	O(n log n)	O(1)
Meeting Rooms II	O(n log n)	O(n)
Interval Intersection	O(m + n)	O(k)

n = number of intervals, k = number of intersections

Common Patterns #

Sort first - Usually by start or end time
Track end time - For detecting overlaps
Two pointers - For intersection problems
Greedy approach - Often optimal for scheduling
Priority queue - For meeting rooms problem
Sweep line - For event-based problems

Best Practices #

Sort appropriately - By start for merging, end for scheduling
Handle edge cases - Empty input, single interval
Check boundaries - Inclusive vs exclusive endpoints
Use proper comparisons - < vs <= matters
Consider time zones - For real-world scheduling
Optimize space - In-place when possible
Binary search - For efficient insertion

Interval problems are common in scheduling and calendar applications. Master these patterns to solve a wide range of interval-based challenges.