Interval Problems Explained

What Are Interval Problems?

Interval problems deal with ranges defined by a start and end point. They appear frequently in coding interviews because they model real-world scenarios like calendar scheduling, resource allocation, and time-based data processing.

An interval is typically represented as a pair [start, end] where start ≤ end. Two intervals overlap if they share at least one point. For example, [1, 5] and[3, 7] overlap because they share the range [3, 5].

The Key Insight: Sort by Start Time

Here's the pattern that unlocks most interval problems: sort the intervals by their start time first. This transforms chaotic, overlapping ranges into a linear sequence you can process one-by-one.

Why does sorting help? After sorting, you only need to compare each interval with the previous one (or a running "merged" interval). You never need to look backward beyond the immediately preceding interval, which gives you O(n) processing after the O(n log n) sort.

// The fundamental pattern for interval problems
function processIntervals(intervals: number[][]): void {
  // Step 1: Sort by start time
  intervals.sort((a, b) => a[0] - b[0])

  // Step 2: Process linearly, comparing with previous
  for (let i = 1; i < intervals.length; i++) {
    const prev = intervals[i - 1]
    const curr = intervals[i]

    // Check for overlap: does current start before previous ends?
    if (curr[0] <= prev[1]) {
      // Overlapping intervals
    } else {
      // Non-overlapping: there's a gap
    }
  }
}

Pattern 1: Merging Overlapping Intervals

The most common interval problem: given a collection of intervals, merge all overlapping intervals into a single list of non-overlapping intervals.

Key insight: Two sorted intervals overlap if the current interval's start is less than or equal to the previous interval's end. When merging, take the maximum of both end points.

function merge(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals

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

  const result: number[][] = [intervals[0]]

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i]
    const lastMerged = result[result.length - 1]

    // Check if current overlaps with last merged interval
    if (current[0] <= lastMerged[1]) {
      // Merge: extend the end of last merged interval
      lastMerged[1] = Math.max(lastMerged[1], current[1])
    } else {
      // No overlap: add current as a new interval
      result.push(current)
    }
  }

  return result
}

// Example:
// Input:  [[1,3], [2,6], [8,10], [15,18]]
// Sorted: [[1,3], [2,6], [8,10], [15,18]]
// Output: [[1,6], [8,10], [15,18]]
//
// [1,3] and [2,6] overlap (2 <= 3), merge to [1,6]
// [8,10] doesn't overlap with [1,6] (8 > 6), keep separate
// [15,18] doesn't overlap with [8,10] (15 > 10), keep separate

Pattern 2: Finding Gaps Between Intervals

Sometimes you need to find the gaps (missing ranges) between intervals. This is useful for finding available time slots in a calendar or identifying missing data ranges.

function findGaps(
  intervals: number[][],
  rangeStart: number,
  rangeEnd: number
): number[][] {
  if (intervals.length === 0) {
    return [[rangeStart, rangeEnd]]
  }

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

  const gaps: number[][] = []
  let currentEnd = rangeStart

  for (const [start, end] of intervals) {
    // If there's a gap before this interval
    if (start > currentEnd) {
      gaps.push([currentEnd, start])
    }

    // Move our pointer forward
    currentEnd = Math.max(currentEnd, end)
  }

  // Check for gap at the end
  if (currentEnd < rangeEnd) {
    gaps.push([currentEnd, rangeEnd])
  }

  return gaps
}

// Example: Find free time slots in a day (0-24)
// Meetings: [[9,10], [12,13], [14,16]]
// Output:   [[0,9], [10,12], [13,14], [16,24]]

Pattern 3: Inserting Into Sorted Intervals

Given a list of non-overlapping intervals sorted by start time, insert a new interval and merge if necessary. This tests your ability to handle edge cases elegantly.

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = []
  let i = 0
  const n = intervals.length

  // Add all intervals that come completely before newInterval
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i])
    i++
  }

  // Merge all intervals that overlap with 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)

  // Add all intervals that come completely after newInterval
  while (i < n) {
    result.push(intervals[i])
    i++
  }

  return result
}

// Example:
// intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]]
// newInterval = [4,8]
//
// Before [4,8]: [[1,2]] (ends before 4)
// Overlap with [4,8]: [3,5], [6,7], [8,10] -> merge to [3,10]
// After [4,8]: [[12,16]]
// Result: [[1,2], [3,10], [12,16]]

Pattern 4: Minimum Meeting Rooms (Interval Scheduling)

Given meeting time intervals, find the minimum number of conference rooms required. This is a classic problem that uses a different approach: track events at boundaries.

Key insight: Instead of thinking about intervals, think about events. A meeting start is +1 room needed, a meeting end is -1 room needed. Sort all events and sweep through them.

function minMeetingRooms(intervals: number[][]): number {
  if (intervals.length === 0) return 0

  // Create events: [time, type] where type is +1 (start) or -1 (end)
  const events: [number, number][] = []

  for (const [start, end] of intervals) {
    events.push([start, 1])   // Meeting starts: need a room
    events.push([end, -1])    // Meeting ends: free a room
  }

  // Sort by time. If times are equal, process ends (-1) before starts (+1)
  // This handles the case where one meeting ends exactly when another starts
  events.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0]
    return a[1] - b[1]  // -1 comes before +1
  })

  let currentRooms = 0
  let maxRooms = 0

  for (const [, delta] of events) {
    currentRooms += delta
    maxRooms = Math.max(maxRooms, currentRooms)
  }

  return maxRooms
}

// Example:
// Input: [[0,30], [5,10], [15,20]]
// Events: [[0,+1], [5,+1], [10,-1], [15,+1], [20,-1], [30,-1]]
//
// time 0:  +1 -> rooms = 1
// time 5:  +1 -> rooms = 2  <- max
// time 10: -1 -> rooms = 1
// time 15: +1 -> rooms = 2
// time 20: -1 -> rooms = 1
// time 30: -1 -> rooms = 0
//
// Answer: 2 rooms needed

Alternative: Using a Min-Heap

Another elegant approach uses a min-heap to track the earliest ending meeting. This simulates actual room allocation.

function minMeetingRoomsHeap(intervals: number[][]): number {
  if (intervals.length === 0) return 0

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

  // Min-heap of end times (rooms in use)
  // In real interviews, you'd use a proper heap implementation
  const endTimes: number[] = []

  for (const [start, end] of intervals) {
    // If earliest ending meeting has finished, reuse that room
    if (endTimes.length > 0 && endTimes[0] <= start) {
      // Remove the earliest end time (room freed)
      endTimes.shift()
    }

    // Add this meeting's end time
    endTimes.push(end)
    endTimes.sort((a, b) => a - b)  // Keep sorted (heap would be O(log n))
  }

  return endTimes.length
}

// The heap size at any point = number of rooms currently in use
// The maximum heap size = minimum rooms needed

Pattern 5: Removing Minimum Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest non-overlapping. This is a greedy problem.

Key insight: Sort by end time, not start time. Always keep the interval that ends earliest - this leaves the most room for future intervals.

function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length <= 1) return 0

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

  let count = 0
  let prevEnd = intervals[0][1]

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i]

    if (start < prevEnd) {
      // Overlap detected - remove current interval (it ends later)
      count++
    } else {
      // No overlap - update the end boundary
      prevEnd = end
    }
  }

  return count
}

// Example:
// Input:  [[1,2], [2,3], [3,4], [1,3]]
// Sorted by end: [[1,2], [2,3], [1,3], [3,4]]
//
// Keep [1,2], prevEnd = 2
// Keep [2,3] (start 2 >= prevEnd 2), prevEnd = 3
// Remove [1,3] (start 1 < prevEnd 3), count = 1
// Keep [3,4] (start 3 >= prevEnd 3)
//
// Answer: Remove 1 interval

Time & Space Complexity

Time Complexity: O(n log n) - Dominated by sorting. The linear scan after sorting is O(n).
Space Complexity: O(1) to O(n) - Depends on whether you create new arrays or sort in-place. The meeting rooms heap solution uses O(n) space.

Common Mistakes to Avoid

• Forgetting to sort: The linear processing only works after sorting
• Wrong sort key: Most problems use start time, but "minimum removals" uses end time
• Off-by-one with boundaries: Is [1,5] and [5,7] overlapping? Depends on the problem definition
• Not handling empty input: Always check for empty or single-element arrays
• Mutating input: Some interviewers expect you to preserve the original array

Practice Problems

Ready to test your understanding? Try these LeetCode problems:

• Easy: Meeting Rooms (LC 252) - Can a person attend all meetings?
• Medium: Merge Intervals (LC 56), Insert Interval (LC 57), Non-overlapping Intervals (LC 435)
• Medium: Meeting Rooms II (LC 253) - Minimum conference rooms needed
• Hard: Employee Free Time (LC 759) - Find common free time across schedules

Continue Learning

• Two Pointers Pattern - Another technique that often uses sorting as a first step
• Greedy Algorithms Guide - Understand why sorting by end time works for interval scheduling
• Heaps and Priority Queues - Essential for the meeting rooms problem
• Start Practicing - Apply interval techniques to real interview problems