Merge Overlapping Intervals in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging overlapping intervals

What is the output of the following code that merges overlapping intervals?

DSA Javascript

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  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;
}

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

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

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

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

D [[1,3],[8,10],[15,18]]

💡 Hint

Think about how intervals that overlap are combined into one.

The code sorts intervals by start time. Then it merges intervals that overlap by updating the end time of the last merged interval.

Here, [1,3] and [2,6] overlap, so they merge into [1,6]. The others remain separate.

❓ Predict Output

intermediate

Result after merging intervals with nested overlaps

What will be printed after merging these intervals?

DSA Javascript

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  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;
}

const intervals = [[1,4],[4,5],[5,6],[7,8]];
console.log(mergeIntervals(intervals));

A [[1,6],[7,8]]

B [[1,4],[4,5],[5,6],[7,8]]

C [[1,5],[5,6],[7,8]]

D [[1,4],[5,6],[7,8]]

💡 Hint

Check how intervals that touch at the edges are merged.

Intervals [1,4], [4,5], and [5,6] all touch or overlap, so they merge into [1,6]. The last interval stays separate.

🔧 Debug

advanced

Identify the error in interval merging code

What error does the following code produce when merging intervals?

DSA Javascript

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  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;
}

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

A No error, but output is incorrect

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

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

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

💡 Hint

Look carefully at the condition that decides when to merge.

The condition uses <= which causes intervals that just touch to not merge correctly, leading to incorrect output but no runtime error.

🧠 Conceptual

advanced

Time complexity of merging intervals

What is the time complexity of merging n intervals using the standard approach of sorting and merging?

A O(log n)

B O(n log n)

C O(n^2)

D O(n)

💡 Hint

Think about the cost of sorting and then one pass merging.

Sorting the intervals takes O(n log n). Merging them in one pass takes O(n). Overall complexity is O(n log n).

🚀 Application

expert

Merging intervals with additional data

Given intervals with an extra label, which option correctly merges overlapping intervals and combines their labels into an array?

DSA Javascript

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

const intervals = [[1,3,'a'],[2,6,'b'],[8,10,'c'],[15,18,'d']];
console.log(mergeIntervalsWithLabels(intervals));

A [[1,3,['a']],[2,6,['b']],[8,10,['c']],[15,18,['d']]]

B [[1,6,['a','b','c']],[15,18,['d']]]

C [[1,6,['a']],[8,10,['c']],[15,18,['d']]]

D [[1,6,['a','b']],[8,10,['c']],[15,18,['d']]]

💡 Hint

Check how labels are combined when intervals merge.

The code merges overlapping intervals and collects their labels in an array. Intervals [1,3,'a'] and [2,6,'b'] merge with labels combined.

Practice

1. What is the main purpose of the Merge Overlapping Intervals algorithm?

easy

A. To sort intervals by their length

B. To combine all intervals that overlap into one continuous interval

C. To find the maximum number of intervals

D. To split intervals into smaller parts

Solution

1. Step 1: Understand the problem goal

   The algorithm aims to merge intervals that share any overlapping range into a single interval.

2. Step 2: Identify the correct purpose

   Among the options, only combining overlapping intervals matches the goal.

3. Final Answer:

   To combine all intervals that overlap into one continuous interval -> Option B

4. Quick Check:

   Merge overlapping intervals = combine overlaps [OK]

Hint: Think about joining intervals that touch or overlap [OK]

Common Mistakes:

• Confusing merging with sorting intervals
• Thinking it splits intervals instead of merging
• Assuming it counts intervals instead of merging

2. Which of the following is the correct way to sort intervals by their start time in JavaScript before merging?

easy

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

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

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

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

Solution

1. Step 1: Identify sorting key for merging

   We must sort intervals by their start time, which is the first element in each interval array.

2. Step 2: Choose correct sort function

   The correct syntax is intervals.sort((a, b) => a[0] - b[0]) to sort ascending by start time.

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort intervals by first element ascending before merging [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Sorting in descending order
• Using wrong array indices for sorting

3. What is the output of the following code?

const intervals = [[1,3],[2,6],[8,10],[15,18]];
function merge(intervals) {
  intervals.sort((a,b) => a[0] - b[0]);
  const merged = [];
  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(merge(intervals));

medium

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

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

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

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

Solution

1. Step 1: Sort intervals by start time

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

2. Step 2: Merge overlapping intervals

   Merge [1,3] and [2,6] into [1,6]. Others remain separate.

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge intervals by comparing end of last merged with start of current [OK]

Common Mistakes:

• Not merging overlapping intervals
• Merging intervals incorrectly by extending wrong boundaries
• Returning original intervals without merging

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

function merge(intervals) {
  intervals.sort((a,b) => a[0] - b[0]);
  const merged = [];
  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;
}

medium

A. The merged array is not initialized correctly

B. The intervals are not sorted before merging

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

D. The max function is used incorrectly

Solution

1. Step 1: Analyze the overlap condition

   The condition uses <= which treats touching intervals as non-overlapping.

2. Step 2: Correct the condition for merging

   Using < instead of <= allows intervals that touch at the boundary to merge correctly.

3. Final Answer:

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

4. Quick Check:

   Overlap check needs <, not <= [OK]

Hint: Use <, not <=, to merge touching intervals [OK]

Common Mistakes:

• Using <= causes missing merges for touching intervals
• Not sorting intervals before merging
• Incorrectly updating merged intervals

5. Given intervals [[1,4],[4,5],[7,9],[8,10]], what is the merged output if intervals that touch at boundaries are considered overlapping?

hard

A. [[1,4],[5,7],[8,10]]

B. [[1,4],[4,5],[7,9],[8,10]]

C. [[1,10]]

D. [[1,5],[7,10]]

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [[1,4],[4,5],[7,9],[8,10]] (already sorted)

2. Step 2: Merge touching and overlapping intervals

   [1,4] and [4,5] touch, so merge to [1,5]. [7,9] and [8,10] overlap, merge to [7,10].

3. Final Answer:

   [[1,5],[7,10]] -> Option D

4. Quick Check:

   Touching intervals merge = [[1,5],[7,10]] [OK]

Hint: Treat touching intervals as overlapping to merge boundaries [OK]

Common Mistakes:

• Not merging intervals that only touch at boundaries
• Merging all intervals incorrectly into one
• Leaving intervals separate despite overlap