Merge Overlapping Intervals in DSA Javascript

Mental Model

We combine intervals that overlap into one bigger interval so no two intervals cover the same range twice.

Analogy: Imagine you have several time blocks booked on a calendar. If some blocks overlap, you merge them into one longer block so you don't double book or count the same time twice.

Intervals before merge:
[1,3] -> [2,6] -> [8,10] -> [15,18]

Intervals after merge:
[1,6] -> [8,10] -> [15,18]

Dry Run Walkthrough

Input: intervals: [[1,3], [2,6], [8,10], [15,18]]

Goal: Merge all overlapping intervals into combined intervals without overlap

Step 1: Sort intervals by start time

[1,3] -> [2,6] -> [8,10] -> [15,18]

Why: Sorting helps us check intervals in order to easily find overlaps

Step 2: Start merged list with first interval [1,3]

merged: [1,3]

Why: We need a place to store merged intervals

Step 3: Compare next interval [2,6] with last merged [1,3], they overlap

merged: [1,3], current: [2,6]

Why: Intervals overlap if current start ≤ last merged end

Step 4: Merge [1,3] and [2,6] into [1,6]

merged: [1,6]

Why: We combine overlapping intervals by extending the end

Step 5: Compare next interval [8,10] with last merged [1,6], no overlap

merged: [1,6] -> [8,10]

Why: No overlap means add interval as is

Step 6: Compare next interval [15,18] with last merged [8,10], no overlap

merged: [1,6] -> [8,10] -> [15,18]

Why: Add last interval since no overlap

Result:

merged intervals: [1,6] -> [8,10] -> [15,18]

Annotated Code

DSA Javascript

class Interval {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

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

  const merged = [];
  merged.push(intervals[0]); // start with first interval

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

    if (current.start <= last.end) {
      // Overlapping intervals, merge by extending end
      last.end = Math.max(last.end, current.end);
    } else {
      // No overlap, add current interval
      merged.push(current);
    }
  }

  return merged;
}

// Driver code
const inputIntervals = [new Interval(1, 3), new Interval(2, 6), new Interval(8, 10), new Interval(15, 18)];
const merged = mergeIntervals(inputIntervals);

// Print merged intervals
for (const interval of merged) {
  console.log(`[${interval.start},${interval.end}]`);
}

intervals.sort((a, b) => a.start - b.start);

Sort intervals by their start time to process in order

merged.push(intervals[0]);

Initialize merged list with first interval

for (let i = 1; i < intervals.length; i++) {

Traverse remaining intervals to merge

if (current.start <= last.end) {

Check if current interval overlaps with last merged

last.end = Math.max(last.end, current.end);

Merge by extending the end of last merged interval

merged.push(current);

Add current interval if no overlap

Output

[1,6]

[8,10]

[15,18]

Complexity Analysis

Time: O(n log n) because we sort all intervals first, then traverse once

Space: O(n) because in worst case no intervals overlap and merged list stores all

vs Alternative: Naive approach compares every pair leading to O(n^2) time, sorting reduces to O(n log n)

Edge Cases

empty intervals list

returns empty list immediately

DSA Javascript

if (intervals.length === 0) return [];

all intervals non-overlapping

merged list equals original intervals

DSA Javascript

else { merged.push(current); }

all intervals overlapping into one

merged list contains single combined interval

DSA Javascript

last.end = Math.max(last.end, current.end);

When to Use This Pattern

When you see a problem asking to combine or simplify overlapping ranges, reach for the merge intervals pattern because sorting and merging in one pass is efficient.

Common Mistakes

Mistake: Not sorting intervals before merging
Fix: Sort intervals by start time first to ensure correct merging order

Mistake: Modifying original intervals without copying
Fix: Be aware that merging modifies intervals in place; copy if original data must stay unchanged

Summary

It merges overlapping intervals into combined intervals without overlap.

Use it when you need to simplify or combine ranges that may overlap.

Sort intervals first, then merge by extending or adding intervals in one pass.

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