Skip to main content

Interval Problems

Interval Problems​

Interval problems are common in algorithmic challenges, dealing with ranges or intervals and often requiring merging, overlapping, or processing intervals in various ways. This document covers fundamental problems related to intervals, including the Merge Intervals problem.

intervals

Utility Methods for interval problems​

/**
 * Check if two intervals overlap.
 * @param {number[]} interval1 - The first interval as [start, end].
 * @param {number[]} interval2 - The second interval as [start, end].
 * @return {boolean} - True if the intervals overlap, otherwise false.
 */
const isOverlapping = (interval1, interval2) => {
  return interval1[0] <= interval2[1] && interval2[0] <= interval1[1];
};

/**
 * Merge two overlapping intervals.
 * @param {number[]} interval1 - The first interval as [start, end].
 * @param {number[]} interval2 - The second interval as [start, end].
 * @return {number[]} - The merged interval as [start, end].
 */
const mergeIntervals = (interval1, interval2) => {
  if (!isOverlapping(interval1, interval2)) {
    throw new Error('Intervals do not overlap.');
  }
  return [Math.min(interval1[0], interval2[0]), Math.max(interval1[1], interval2[1])];
};

/**
 * Find all overlapping intervals with a given interval from a list of intervals.
 * @param {number[][]} intervals - A list of intervals, each represented as [start, end].
 * @param {number[]} interval - The interval to check for overlaps.
 * @return {number[][]} - A list of overlapping intervals.
 */
const findOverlappingIntervals = (intervals, interval) => {
  return intervals.filter(otherInterval => isOverlapping(otherInterval, interval));
};

// Example usage:

// Define some intervals
const interval1 = [1, 5];
const interval2 = [4, 8];
const interval3 = [10, 15];
const intervalToFind = [3, 6];
const intervalsList = [[1, 5], [6, 10], [15, 20]];

// Check if intervals overlap
console.log(isOverlapping(interval1, interval2)); // Output: true
console.log(isOverlapping(interval1, interval3)); // Output: false

// Merge overlapping intervals
console.log(mergeIntervals(interval1, interval2)); // Output: [1, 8]

// Find overlapping intervals
console.log(findOverlappingIntervals(intervalsList, intervalToFind)); // Output: [[1, 5]]

Merge Intervals​

Problem Statement: Given a collection of intervals, merge all overlapping intervals.

Example:

/**
 * Merge overlapping intervals.
 * @param {number[][]} intervals - A list of intervals where each interval is represented as [start, end].
 * @return {number[][]} - The merged list of intervals.
 */
const mergeIntervals = (intervals) => {
  if (intervals.length === 0) return [];

  // Sort intervals by their starting point
  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 lastMerged = merged[merged.length - 1];

    if (current[0] <= lastMerged[1]) {
      // Overlapping intervals, merge them
      lastMerged[1] = Math.max(lastMerged[1], current[1]);
    } else {
      // No overlap, add the current interval
      merged.push(current);
    }
  }

  return merged;
}

// Example usage:
const intervals = [[1, 3], [2, 6], [8, 10], [15, 18]];
console.log(mergeIntervals(intervals)); 
// Output: [[1, 6], [8, 10], [15, 18]]

Insert Interval​

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

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

  // Merge all overlapping intervals with the new interval
  while (i < n && isOverlapping(intervals[i], newInterval)) {
    newInterval = merge(intervals[i++], newInterval);
  }
  result.push(newInterval);

  // Add all intervals that come after the new interval
  while (i < n) {
    result.push(intervals[i++]);
  }

  return result;
};

Finding an Interval Containing a Point​

const findOverlappingIntervals = (intervals, x) => {
  let left = 0
  let right = intervals.length - 1

  while (left <= right) {
    const mid = left + right >>> 1
    const [s, e] = intervals[mid]
    if (s <= x && x <= e) return intervals[mid]
    else if (x < s) right = mid - 1
    else left = mid + 1
  }
  return null
}

// Test Intervals
const intervals = [
    [1, 5],
    [10, 15],
    [20, 25],
    [30, 35],
    [40, 50]
];

// Test cases for `findIntervalContainingPoint`

// Case 1: Point lies within an interval
console.log(findIntervalContainingPoint(intervals, 3)); // Expected output: [1, 5]

// Case 2: Point lies exactly on the start of an interval
console.log(findIntervalContainingPoint(intervals, 10)); // Expected output: [10, 15]

// Case 3: Point lies exactly on the end of an interval
console.log(findIntervalContainingPoint(intervals, 25)); // Expected output: [20, 25]

// Case 4: Point lies between intervals
console.log(findIntervalContainingPoint(intervals, 6)); // Expected output: null

// Case 5: Point is smaller than the smallest interval
console.log(findIntervalContainingPoint(intervals, 0)); // Expected output: null

// Case 6: Point is larger than the largest interval
console.log(findIntervalContainingPoint(intervals, 55)); // Expected output: null

Finding Overlapping Intervals with a Target Interval​

function findOverlappingIntervals(intervals, targetStart, targetEnd) {
  let left = 0, right = intervals.length - 1;
  const overlappingIntervals = [];

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const [start, end] = intervals[mid];

    if (end < targetStart) {
      // Move right if the interval is entirely before the target
      left = mid + 1;
    } else if (start > targetEnd) {
      // Move left if the interval is entirely after the target
      right = mid - 1;
    } else {
      // Overlap detected, so add to result
      overlappingIntervals.push(intervals[mid]);

      // Check both sides of mid for additional overlapping intervals
      let i = mid - 1;
      while (i >= 0 && intervals[i][1] >= targetStart) overlappingIntervals.push(intervals[i--]);

      i = mid + 1;
      while (i < intervals.length && intervals[i][0] <= targetEnd) overlappingIntervals.push(intervals[i++]);

      break;
    }
  }

  return overlappingIntervals;
}

const intervals = [
  [1, 5],
  [10, 15],
  [20, 25],
  [30, 35],
  [40, 50]
];


// Case 1: Target interval completely overlaps one interval
console.log(findOverlappingIntervals(intervals, 12, 14)); // Expected output: [[10, 15]]

// Case 2: Target interval overlaps multiple intervals
console.log(findOverlappingIntervals(intervals, 15, 30)); // Expected output: [[10, 15], [20, 25], [30, 35]]

// Case 3: Target interval is completely outside (before) any intervals
console.log(findOverlappingIntervals(intervals, -5, -1)); // Expected output: []

// Case 4: Target interval is completely outside (after) any intervals
console.log(findOverlappingIntervals(intervals, 60, 70)); // Expected output: []

// Case 5: Target interval overlaps exactly at the boundary of two intervals
console.log(findOverlappingIntervals(intervals, 5, 10)); // Expected output: [[1, 5], [10, 15]]

// Case 6: Target interval covers all intervals
console.log(findOverlappingIntervals(intervals, 0, 55)); // Expected output: [[1, 5], [10, 15], [20, 25], [30, 35], [40, 50]]

// Case 7: Target interval does not overlap any intervals
console.log(findOverlappingIntervals(intervals, 6, 9)); // Expected output: []

Intervals Problems​