Merge Overlapping Intervals in DSA Typescript - 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 helps you join those overlapping parts so you get fewer, bigger intervals without any overlaps.

Why it matters

Without merging overlapping intervals, you might count the same time or space multiple times, causing confusion or errors. For example, scheduling meetings or booking rooms would be messy if overlapping times are treated separately. Merging intervals simplifies 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 explore interval trees, advanced scheduling algorithms, or problems involving ranges and coverage.

Mental Model

Core Idea

Combine intervals that touch or overlap into one continuous interval to avoid counting the same range multiple times.

Think of it like...

It's like putting together puzzle pieces that fit or overlap to form a bigger picture without gaps or repeats.

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

Sorted and merged intervals:
[1,6] [8,10] [15,18]

Diagram:
┌─────┐
│1  3 │
  ┌───────┐
  │2     6│
          ┌───┐
          │8 10│
                 ┌─────┐
                 │15 18│

Build-Up - 7 Steps

1

Foundation

Understanding Intervals and Overlaps

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

An interval is a range with a start and end, like [1,3]. Two intervals overlap if they share any points. For example, [1,3] and [2,6] overlap because 2 and 3 are in both.

Result

You can identify overlapping intervals by comparing their start and end points.

Understanding what makes intervals overlap is the base for merging them correctly.

2

Foundation

Sorting Intervals by Start Time

Concept: Sort intervals by their start value to process them in order.

Given intervals like [8,10], [1,3], [2,6], sort them by start: [1,3], [2,6], [8,10]. Sorting helps us check overlaps in a single pass.

Result

Intervals are arranged from earliest start to latest, making merging easier.

Sorting is crucial because it lets us merge intervals by moving forward without missing overlaps.

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, merge intervals by comparing each with the last merged interval.

Start with the first interval as merged. For each next interval, if it starts before or at the end of the last merged interval, extend the last merged interval's end if needed. Otherwise, add it as a new merged interval.

Result

Overlapping intervals combine into one, non-overlapping list remains.

Knowing you only need to compare with the last merged interval simplifies the process and improves efficiency.

4

Intermediate

Implementing Merge in TypeScript

🤔Before reading on: do you think the merge function should modify the original array or create a new one? Commit to your answer.

Concept: Write a function that sorts and merges intervals, returning a new list.

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

Result

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

Implementing the algorithm in code cements understanding and shows how sorting and merging work together.

5

Intermediate

Handling Edge Cases in Merging

🤔Before reading on: do you think intervals that just touch (like [1,2] and [2,3]) should merge? Commit to your answer.

Concept: Decide how to treat intervals that meet exactly at endpoints and handle empty or single-element inputs.

Intervals that touch at endpoints can be merged if you consider touching as overlapping. For example, [1,2] and [2,3] merge into [1,3]. Also, if input is empty or has one interval, return it as is.

Result

Merging treats touching intervals as overlapping, producing fewer intervals.

Clarifying how to handle touching intervals avoids bugs and ensures consistent results.

6

Advanced

Optimizing for Large Interval Sets

🤔Before reading on: do you think sorting is the biggest time cost in merging intervals? Commit to your answer.

Concept: Understand that sorting dominates time complexity and explore ways to optimize or handle large data.

Sorting takes O(n log n) time, which is the main cost. Merging after sorting is O(n). For very large data, consider streaming intervals sorted by start or using balanced trees to insert and merge on the fly.

Result

Efficient merging even with millions of intervals by focusing on sorting and data structure choice.

Recognizing sorting as the bottleneck guides optimization and helps design scalable solutions.

7

Expert

Merging Intervals in Real-Time Systems

🤔Before reading on: do you think the same merge approach works when intervals arrive one by one in real time? Commit to your answer.

Concept: Explore how to merge intervals dynamically as new intervals arrive without re-sorting all data.

In real-time, keep merged intervals in a balanced tree or list. For each new interval, find where it fits, merge overlapping neighbors, and update the structure. This avoids full re-sorting and supports fast queries.

Result

Dynamic merging supports live updates and queries efficiently.

Understanding dynamic merging reveals how to adapt static algorithms for real-world, continuous data streams.

Under the Hood

The algorithm first sorts intervals by their start time so that overlapping intervals appear next to each other. Then it iterates through the sorted list, comparing the current interval with the last merged interval. If they overlap or touch, it extends the last merged interval's end to cover both. Otherwise, it adds the current interval as a new merged interval. This process ensures all overlapping or touching intervals combine into one continuous interval.

Why designed this way?

Sorting first simplifies the problem by ordering intervals so only adjacent intervals need comparison, reducing complexity from checking all pairs to a single pass. Alternatives like checking every pair would be inefficient (O(n²)). This design balances simplicity and performance, making it practical for many applications.

Input intervals:
┌─────┐ ┌───────┐       ┌───┐          ┌─────┐
│1  3 │ │2     6│       │8 10│          │15 18│
└─────┘ └───────┘       └───┘          └─────┘

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 new interval
Compare with [15,18]: no overlap, add new interval

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

Myth Busters - 4 Common Misconceptions

Quick: Do intervals that only touch at endpoints count as overlapping? Commit to yes or no.

Common Belief: Intervals must overlap by at least one point inside their ranges to merge.

Reality: Intervals that touch exactly at endpoints (like [1,2] and [2,3]) are usually merged because they form a continuous range.

Why it matters: Not merging touching intervals can cause unnecessary splits and incorrect counts in coverage or scheduling.

Quick: Is it necessary to compare every interval with all others to merge? Commit to yes or no.

Common Belief: You must check every pair of intervals to find overlaps.

Reality: Sorting intervals by start time lets you merge by only comparing each interval with the last merged one, reducing complexity.

Why it matters: Checking all pairs wastes time and makes the algorithm slow for large inputs.

Quick: Does merging intervals always reduce the number of intervals? Commit to yes or no.

Common Belief: Merging intervals always reduces the total count of intervals.

Reality: If no intervals overlap or touch, merging returns the same number of intervals.

Why it matters: Expecting fewer intervals can mislead you to think merging always changes data, but sometimes data is already non-overlapping.

Quick: Can you merge intervals without sorting first? Commit to yes or no.

Common Belief: Sorting is optional; you can merge intervals in any order.

Reality: Without sorting, you risk missing overlaps because intervals are unordered, leading to incorrect merges.

Why it matters: Skipping sorting causes bugs and incorrect results, especially with complex or large data.

Expert Zone

1

Merging intervals in-place can save memory but requires careful handling to avoid overwriting data before it's processed.

2

The choice of data structure for storing merged intervals affects performance in dynamic or repeated merge scenarios.

3

Floating point intervals or intervals with open/closed ends require special handling to define overlap precisely.

When NOT to use

When intervals are extremely large or streaming continuously, static merging is inefficient. Instead, use interval trees or segment trees for fast queries and updates. Also, if intervals have complex constraints like weights or priorities, specialized algorithms are better.

Production Patterns

In real-world systems, merging intervals is used in calendar apps to combine busy times, in network systems to merge IP ranges, and in databases to optimize range queries. Often, merged intervals are stored in balanced trees or indexed structures for fast access.

Connections

Interval Trees

Builds-on

Understanding merging intervals helps grasp interval trees, which store intervals efficiently and support fast overlap queries.

Sweep Line Algorithm

Same pattern

Merging intervals uses a sweep line approach by sorting and scanning intervals in order, a pattern common in computational geometry.

Project Management Scheduling

Application

Merging overlapping intervals mirrors combining overlapping tasks in project timelines to find free or busy periods.

Common Pitfalls

#1 Failing to sort intervals before merging.

Wrong approach:

function mergeIntervals(intervals: number[][]): number[][] {
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;
}

Correct approach:

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

Root cause:

Not sorting means intervals are processed in random order, so overlaps can be missed or merged incorrectly.

#2 Not updating the end of the merged interval correctly.

Wrong approach:

if (intervals[i][0] <= last[1]) {
last[1] = intervals[i][1]; // Incorrect: overwrites without max
}

Correct approach:

if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
}

Root cause:

Failing to take the maximum end causes loss of coverage when the new interval extends beyond the current merged end.

#3 Treating touching intervals as non-overlapping.

Wrong approach:

if (intervals[i][0] < last[1]) { // strict less than
// merge
}

Correct approach:

if (intervals[i][0] <= last[1]) { // less than or equal
// merge
}

Root cause:

Using strict less than misses intervals that meet exactly at endpoints, causing unnecessary splits.

Key Takeaways

Merging overlapping intervals combines ranges that share points into one continuous range to simplify data.

Sorting intervals by start time is essential to efficiently merge by comparing only adjacent intervals.

Touching intervals at endpoints are usually merged to represent continuous coverage accurately.

The main cost in merging intervals is sorting; merging itself is a simple linear pass.

Dynamic or large-scale interval merging requires advanced data structures beyond the basic algorithm.

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