Merge Overlapping Intervals in DSA Javascript - Deep Dive

Overview - Merge Overlapping Intervals

What is it?

Merge Overlapping Intervals is a way to combine intervals that share some common part into one bigger interval. Imagine you have many time slots or ranges, and some of them overlap or touch each other. This method finds those overlaps and merges them so that you get fewer, bigger intervals without any overlaps.

Why it matters

Without merging overlapping intervals, you might count the same time or range multiple times, causing confusion or errors. For example, if you schedule meetings or book rooms, overlapping times can cause double bookings. Merging helps simplify and organize data, making it easier to understand and use.

Where it fits

Before learning this, you should understand arrays and sorting basics. After this, you can learn about interval trees or advanced scheduling algorithms that handle dynamic intervals efficiently.

Mental Model

Core Idea

If two intervals overlap or touch, combine them into one bigger interval to avoid repetition.

Think of it like...

Think of intervals as pieces of tape on a table. If two pieces overlap or touch, you peel them off and replace them with one longer piece covering the same area.

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

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

Build-Up - 6 Steps

1

Foundation

Understanding Intervals and Overlaps

Concept: What intervals are and how to tell if two intervals overlap.

An interval is a pair of numbers showing a start and end, like [1,3]. Two intervals overlap if one starts before the other ends and ends after the other starts. For example, [1,3] and [2,6] overlap because 2 is between 1 and 3.

Result

You can identify if two intervals share any common points.

Knowing how to detect overlap is the first step to merging intervals correctly.

2

Foundation

Sorting Intervals by Start Time

Concept: Sorting intervals helps process them in order to merge easily.

Sort all intervals by their start value from smallest to largest. For example, given intervals [8,10], [1,3], [2,6], sorting them gives [1,3], [2,6], [8,10]. This order helps us check overlaps in a single pass.

Result

Intervals are arranged so that overlapping ones come next to each other.

Sorting simplifies the problem by putting intervals in a predictable order.

3

Intermediate

Merging Overlapping Intervals Step-by-Step

🤔Before reading on: do you think merging requires checking all pairs or just adjacent intervals after sorting? Commit to your answer.

Concept: After sorting, only adjacent intervals need to be checked for overlap to merge.

Start with the first interval as the current merged interval. For each next interval, check if it overlaps with the current merged one. If yes, extend the current merged interval's end to the max end of both. If no, add the current merged interval to the result and move to the next interval.

Result

A list of merged intervals with no overlaps.

Understanding that only adjacent intervals after sorting can overlap reduces complexity and makes merging efficient.

4

Intermediate

Implementing Merge in JavaScript

🤔Before reading on: do you think using a new array for merged intervals or modifying in place is better? Commit to your answer.

Concept: Use a new array to store merged intervals while iterating through sorted intervals.

```javascript function mergeIntervals(intervals) { if (intervals.length === 0) return []; intervals.sort((a, b) => a[0] - b[0]); const merged = []; let current = intervals[0]; for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] <= current[1]) { current[1] = Math.max(current[1], intervals[i][1]); } else { merged.push(current); current = intervals[i]; } } merged.push(current); return merged; } // Example usage: console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]])); ```

Result

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

Using a separate array for merged intervals keeps the original data safe and makes the logic clear.

5

Advanced

Handling Edge Cases and Empty Inputs

🤔Before reading on: do you think empty or single-interval inputs need special handling? Commit to your answer.

Concept: Consider cases with no intervals or only one interval to avoid errors.

If the input array is empty, return an empty array immediately. If there is only one interval, return it as is. This prevents errors and unnecessary processing.

Result

The function safely handles all input sizes.

Accounting for edge cases prevents runtime errors and makes the function robust.

6

Expert

Optimizing for Large Datasets and Real-Time Merging

🤔Before reading on: do you think sorting is always the best approach for merging intervals in real-time? Commit to your answer.

Concept: For very large or streaming data, sorting every time is costly; data structures like interval trees can help.

When intervals arrive continuously, sorting each time is inefficient. Interval trees or balanced binary search trees can store intervals and merge overlaps dynamically. These structures allow fast insertion and querying of overlapping intervals without full sorting.

Result

Efficient merging in real-time or large-scale systems.

Knowing advanced data structures helps scale merging beyond simple batch processing.

Under the Hood

The algorithm first sorts intervals by their start time so that any overlapping intervals appear next to each other. Then it iterates once through the sorted list, comparing the current interval with the last merged interval. If they overlap, it merges by extending the end time. Otherwise, it adds the current interval as a new merged interval. This single pass after sorting ensures O(n log n) time complexity due to sorting, with O(n) merging.

Why designed this way?

Sorting first reduces the problem complexity by ordering intervals, so only neighbors need checking. This avoids comparing every pair, which would be slower (O(n^2)). The design balances simplicity and efficiency, making it practical for many applications.

Sorted intervals:
┌─────────┐ ┌─────────────┐ ┌───────┐ ┌─────────────┐
│ [1, 3]  │ │  [2, 6]     │ │[8,10] │ │  [15, 18]   │
└─────────┘ └─────────────┘ └───────┘ └─────────────┘

Merging process:
Start with [1,3]
  Compare with [2,6] -> overlap, merge to [1,6]
  Compare with [8,10] -> no overlap, add [1,6] to result, move to [8,10]
  Compare with [15,18] -> no overlap, add [8,10] to result, move to [15,18]
Add last interval [15,18] to result

Myth Busters - 3 Common Misconceptions

Quick: Do you think intervals that only touch at endpoints should be merged? Commit yes or no.

Common Belief: Intervals that only touch at endpoints, like [1,2] and [2,3], are separate and should not be merged.

Reality: Intervals that touch at endpoints are usually merged because they represent continuous coverage without gaps.

Why it matters: Not merging touching intervals can cause unnecessary fragmentation and incorrect calculations of coverage or availability.

Quick: Do you think sorting intervals by end time instead of start time works for merging? Commit yes or no.

Common Belief: Sorting intervals by their end time is just as good as sorting by start time for merging.

Reality: Sorting by start time is necessary because merging depends on the order intervals begin, ensuring overlaps are checked correctly.

Why it matters: Sorting by end time can miss overlaps or cause incorrect merges, leading to wrong results.

Quick: Do you think merging intervals can be done without sorting? Commit yes or no.

Common Belief: You can merge overlapping intervals without sorting them first.

Reality: Without sorting, you must compare every pair of intervals, which is inefficient and complex.

Why it matters: Skipping sorting leads to slower algorithms (O(n^2)) and harder-to-maintain code.

Expert Zone

1

Merging intervals assumes intervals are closed or half-open consistently; mixing types can cause subtle bugs.

2

In-place merging is possible but often avoided to keep input data intact and avoid side effects.

3

When intervals have additional data (like labels), merging requires deciding how to combine or preserve that data.

When NOT to use

For dynamic interval sets with frequent insertions and deletions, use interval trees or segment trees instead of batch merging. Also, if intervals represent non-continuous data, merging may lose important distinctions.

Production Patterns

Used in calendar apps to combine busy times, in network systems to merge IP ranges, and in computational geometry for union of shapes. Often combined with sorting and binary search for efficient querying.

Connections

Interval Trees

Builds-on

Understanding merging intervals helps grasp interval trees, which manage overlapping intervals dynamically and efficiently.

Sorting Algorithms

Depends-on

Merging intervals relies on sorting; knowing sorting algorithms deeply improves merging performance and understanding.

Project Management Scheduling

Application

Merging overlapping intervals models how project tasks or meetings are combined to avoid conflicts and optimize resource use.

Common Pitfalls

#1 Not sorting intervals before merging.

Wrong approach:

function mergeIntervals(intervals) {
const merged = [];
let current = intervals[0];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= current[1]) {
current[1] = Math.max(current[1], intervals[i][1]);
} else {
merged.push(current);
current = intervals[i];
}
}
merged.push(current);
return merged;
}

Correct approach:

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

Root cause:

Forgetting that intervals must be ordered to correctly identify overlaps.

#2 Merging intervals that only touch at endpoints as separate.

Wrong approach:

if (intervals[i][0] < current[1]) { // strict less than
current[1] = Math.max(current[1], intervals[i][1]);
}

Correct approach:

if (intervals[i][0] <= current[1]) { // less than or equal
current[1] = Math.max(current[1], intervals[i][1]);
}

Root cause:

Misunderstanding that touching intervals represent continuous coverage.

#3 Modifying input intervals directly without copying.

Wrong approach:

function mergeIntervals(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= intervals[i-1][1]) {
intervals[i-1][1] = Math.max(intervals[i-1][1], intervals[i][1]);
intervals.splice(i, 1);
i--;
}
}
return intervals;
}

Correct approach:

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

Root cause:

Trying to optimize by modifying input leads to bugs and side effects.

Key Takeaways

Merging overlapping intervals simplifies data by combining ranges that share common parts.

Sorting intervals by start time is essential to efficiently find and merge overlaps.

Only adjacent intervals after sorting need to be checked for overlap, reducing complexity.

Edge cases like empty inputs or touching intervals must be handled carefully for correctness.

Advanced data structures like interval trees help when intervals change dynamically or datasets are large.

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