Merge Overlapping Intervals in DSA Javascript - Execution Trace

Concept Flow - Merge Overlapping Intervals

Sort intervals by start

↓

Initialize merged list empty

↓

For each interval

↓

Check overlap with last merged

↓

Merge intervals

↓

Repeat

↓

Return merged

Sort intervals first, then go through each interval to merge if overlapping or add if not.

Execution Sample

DSA Javascript

const intervals = [[1,3],[2,6],[8,10],[15,18]];
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]);
  }
}

Sort intervals by start, then merge overlapping intervals into one list.

Execution Table

Step	Operation	Current Interval	Last Merged Interval	Action	Merged List State
1	Sort intervals	N/A	N/A	Sorted intervals: [[1,3],[2,6],[8,10],[15,18]]	[]
2	Process interval	[1,3]	N/A	Merged empty, add interval	[[1,3]]
3	Process interval	[2,6]	[1,3]	Overlap detected, merge to [1,6]	[[1,6]]
4	Process interval	[8,10]	[1,6]	No overlap, add interval	[[1,6],[8,10]]
5	Process interval	[15,18]	[8,10]	No overlap, add interval	[[1,6],[8,10],[15,18]]
6	End	N/A	N/A	All intervals processed	[[1,6],[8,10],[15,18]]

💡 All intervals processed and merged where overlapping.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
intervals	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]
merged	[]	[[1,3]]	[[1,6]]	[[1,6],[8,10]]	[[1,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]
interval (current)	N/A	[1,3]	[2,6]	[8,10]	[15,18]	N/A
last merged	N/A	[1,3]	[1,6]	[8,10]	[15,18]	[15,18]

Key Moments - 3 Insights

Why do we sort intervals before merging?

Sorting ensures intervals are in order by start time, so overlapping intervals come one after another. This is shown in execution_table step 1 where intervals are sorted before processing.

How do we know if two intervals overlap?

We check if the start of the current interval is less than or equal to the end of the last merged interval. If yes, they overlap and we merge. See execution_table step 3 where [2,6] overlaps with [1,3].

What happens if intervals do not overlap?

If no overlap, we add the current interval as a new separate interval in merged list. This is shown in steps 4 and 5 where intervals [8,10] and [15,18] are added separately.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the merged list state after merging?

A [[1,3],[2,6]]

B [[2,6]]

C [[1,6]]

D [[1,3]]

💡 Hint

Check the 'Merged List State' column at step 3 in execution_table.

At which step does the condition for no overlap first occur?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Action' column in execution_table where it says 'No overlap, add interval'.

If the input intervals were [[1,4],[4,5]], how would the merged list change after processing both?

A [[1,5]]

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

C [[4,5]]

D [[1,4]]

💡 Hint

Check how overlapping intervals are merged by comparing current interval start with last merged end.

Concept Snapshot

Merge Overlapping Intervals:
1. Sort intervals by start time.
2. Initialize empty merged list.
3. For each interval:
   - If no overlap with last merged, add it.
   - Else merge by updating end time.
4. Return merged list with no overlaps.

Full Transcript

To merge overlapping intervals, first sort the intervals by their start times. Then create an empty list to hold merged intervals. Go through each interval one by one. If the merged list is empty or the current interval does not overlap with the last merged interval, add it to the merged list. If it overlaps, merge by updating the end time of the last merged interval to the maximum end time between the two. Continue until all intervals are processed. The result is a list of intervals with no overlaps.

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