Merge Overlapping Intervals in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of merging these intervals?

Given the intervals [[1,3],[2,6],[8,10],[15,18]], what is the merged list of intervals?

DSA Typescript

function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const interval of intervals) {
    if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }
  return merged;
}

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

A [[1,6],[8,10],[15,18]]

B [[1,3],[2,6],[8,10],[15,18]]

C [[1,10],[15,18]]

D [[1,6],[8,18]]

💡 Hint

Sort intervals by start time and merge overlapping ones by updating the end time.

The intervals [1,3] and [2,6] overlap, so they merge into [1,6]. The others do not overlap.

❓ Predict Output

intermediate

What is the output after merging these intervals?

Given intervals [[1,4],[4,5]], what is the merged list of intervals?

DSA Typescript

function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const interval of intervals) {
    if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }
  return merged;
}

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

A [[1,5]]

B [[1,4],[4,5]]

C [[1,4],[5,5]]

D [[1,9]]

💡 Hint

Intervals that touch at the boundary should be merged.

The intervals [1,4] and [4,5] touch at 4, so they merge into [1,5].

🔧 Debug

advanced

Identify the error in this merge intervals code

What error will this code produce when merging intervals [[1,4],[2,3]]?

DSA Typescript

function mergeIntervals(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const interval of intervals) {
    if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }
  return merged;
}

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

A No error, output: [[1,4],[2,3]]

B No error, output: [[1,3]]

C No error, output: [[1,4]]

D Runtime error: TypeError

💡 Hint

Check the condition that decides when to merge intervals.

The condition uses <= which causes intervals that touch at the boundary not to merge properly. But here, intervals overlap so merging works fine.

🧠 Conceptual

advanced

How many intervals remain after merging [[1,5],[2,3],[4,6],[7,8]]?

After merging overlapping intervals in [[1,5],[2,3],[4,6],[7,8]], how many intervals remain?

A 3

B 2

C 4

D 1

💡 Hint

Merge intervals that overlap or touch.

The first three intervals overlap and merge into [1,6]. The last interval [7,8] does not overlap. So total 2 intervals remain.

🚀 Application

expert

What is the merged output for these intervals with nested overlaps?

Given intervals [[1,10],[2,5],[6,9],[11,15],[14,18]], what is the merged list of intervals?

DSA Typescript

function mergeIntervals(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const interval of intervals) {
    if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }
  return merged;
}

console.log(mergeIntervals([[1,10],[2,5],[6,9],[11,15],[14,18]]));

A [[1,9],[11,18]]

B [[1,10],[2,5],[6,9],[11,15],[14,18]]

C [[1,18]]

D [[1,10],[11,18]]

💡 Hint

Nested intervals inside [1,10] merge into it; [11,15] and [14,18] merge separately.

The intervals [2,5] and [6,9] are inside [1,10], so merged into [1,10]. Intervals [11,15] and [14,18] overlap and merge into [11,18].

Practice

1. What is the main purpose of merging overlapping intervals in a list of intervals?

easy

A. To split intervals into smaller parts

B. To sort intervals by their end times only

C. To remove all intervals that have the same start time

D. To combine intervals that overlap into a single continuous interval

Solution

1. Step 1: Understand overlapping intervals

   Overlapping intervals share some common range, so merging combines them into one continuous interval.

2. Step 2: Purpose of merging

   Merging removes overlaps by creating a single interval covering all overlapping parts.

3. Final Answer:

   To combine intervals that overlap into a single continuous interval -> Option D

4. Quick Check:

   Merging = Combine overlaps [OK]

Hint: Merge means combine overlapping parts into one [OK]

Common Mistakes:

• Thinking merging sorts intervals only
• Confusing merging with removing duplicates
• Believing merging splits intervals

2. Which of the following TypeScript code snippets correctly sorts an array of intervals by their start time?

easy

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

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

C. intervals.sort((a, b) => a[1] + b[0]);

D. intervals.sort((a, b) => a[0] + b[1]);

Solution

1. Step 1: Identify sorting by start time

   Sorting by start time means comparing the first element of each interval (a[0] and b[0]).

2. Step 2: Check correct comparison function

   Subtracting a[0] - b[0] sorts ascending by start time, which is correct.

3. Final Answer:

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

4. Quick Check:

   Sort by start = a[0] - b[0] [OK]

Hint: Sort intervals by start using a[0] - b[0] [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Adding values instead of subtracting in sort
• Using wrong indices for comparison

3. What is the output of the following TypeScript code?

function mergeIntervals(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const interval of intervals) {
    if (!merged.length || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }
  return merged;
}

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

medium

A. [[1,3],[2,6],[8,10],[15,18]]

B. [[1,10],[15,18]]

C. [[1,6],[8,10],[15,18]]

D. [[2,6],[8,10],[15,18]]

Solution

1. Step 1: Sort intervals by start

   Sorted intervals: [[1,3],[2,6],[8,10],[15,18]] (already sorted)

2. Step 2: Merge overlapping intervals

   First interval [1,3] added.
   Second interval [2,6] overlaps with [1,3], merge to [1,6].
   Third interval [8,10] no overlap, add.
   Fourth interval [15,18] no overlap, add.

3. Final Answer:

   [[1,6],[8,10],[15,18]] -> Option C

4. Quick Check:

   Merged intervals = [[1,6],[8,10],[15,18]] [OK]

Hint: Sort first, then merge overlapping intervals step-by-step [OK]

Common Mistakes:

• Not sorting intervals before merging
• Overwriting intervals incorrectly
• Missing to merge overlapping intervals

4. The following TypeScript function is intended to merge overlapping intervals but has a bug. What is the bug?

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const result: number[][] = [];
  for (let i = 0; i < intervals.length; i++) {
    if (result.length === 0 || result[result.length - 1][1] <= intervals[i][0]) {
      result.push(intervals[i]);
    } else {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1]);
    }
  }
  return result;
}

medium

A. The max function is used incorrectly

B. The condition should use '<' instead of '<=' to detect overlap

C. The function does not handle empty input

D. The intervals are not sorted before merging

Solution

1. Step 1: Analyze overlap condition

   Condition uses '<=' which treats touching intervals as non-overlapping.

2. Step 2: Correct overlap detection

   Correct condition uses '<' so that when last_end == current_start (touching), it merges since the if condition fails and goes to else. Current '<=' incorrectly pushes new for touching intervals.

3. Final Answer:

   The condition should use '<' instead of '<=' to detect overlap -> Option B

4. Quick Check:

   Overlap check needs '<' not '<=' [OK]

Hint: Use '<' to detect overlap, not '<=' [OK]

Common Mistakes:

• Using '<=' causes missing merges on touching intervals
• Ignoring sorting requirement
• Not checking empty input but that is not the bug here

5. Given a list of intervals, how would you modify the merge overlapping intervals algorithm to also count how many original intervals were merged into each resulting interval?
Choose the best approach.

hard

A. Keep a count alongside each merged interval and increment it when merging overlaps

B. Sort intervals by end time instead of start time

C. Use a separate array to store counts and update only after merging all intervals

D. Merge intervals normally and count the total number of intervals merged at the end

Solution

1. Step 1: Track counts during merging

   When merging intervals, keep a count for each merged interval starting at 1.

2. Step 2: Increment count on overlap

   Each time an interval merges into the last merged interval, increment its count to reflect how many intervals combined.

3. Final Answer:

   Keep a count alongside each merged interval and increment it when merging overlaps -> Option A

4. Quick Check:

   Count merges while merging intervals [OK]

Hint: Track counts during merge, increment on overlap [OK]

Common Mistakes:

• Sorting by end time does not help counting merges
• Counting after merging loses interval mapping
• Counting total merges instead of per merged interval