Merge Overlapping Intervals in DSA C - 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 you get fewer, bigger intervals without any overlaps.

Why it matters

Without merging overlapping intervals, we might treat overlapping time slots or ranges as separate, causing confusion or errors. For example, scheduling meetings or booking rooms would be inefficient or incorrect. Merging helps simplify data, reduce complexity, and make decisions clearer and faster.

Where it fits

Before learning this, you should understand arrays and sorting basics. After mastering merging intervals, you can explore interval trees, scheduling algorithms, and advanced range queries.

Mental Model

Core Idea

If two intervals overlap or touch, combine them into one continuous interval to avoid duplication or conflict.

Think of it like...

Imagine you have several pieces of tape on a table, some overlapping. Instead of many small pieces, you want to glue them into fewer longer strips without gaps or overlaps.

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

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

Process:
Sort intervals by start -> Compare current interval with last merged -> If overlap, merge -> Else, add new interval

Build-Up - 7 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 [start, end] representing a range. Two intervals overlap if one starts before the other ends and vice versa. For example, [1,3] and [2,6] overlap because 2 ≤ 3.

Result

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

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

2

Foundation

Sorting Intervals by Start Time

Concept: Sorting intervals helps organize them so overlaps are easier to find.

Sort all intervals by their start value in ascending order. For example, given intervals [8,10], [1,3], [2,6], after sorting: [1,3], [2,6], [8,10].

Result

Sorted intervals allow a simple linear scan to find overlaps.

Sorting reduces the problem from checking all pairs to just comparing neighbors.

3

Intermediate

Merging Two Overlapping Intervals

🤔Before reading on: If intervals [1,4] and [3,5] overlap, what is their merged interval? Commit to your answer.

Concept: How to combine two overlapping intervals into one.

If intervals overlap, the merged interval starts at the smaller start and ends at the larger end. For example, merging [1,4] and [3,5] results in [1,5].

Result

You get a single interval covering both original intervals without gaps.

Knowing how to merge two intervals is the building block for merging many intervals.

4

Intermediate

Iterative Merging of Sorted Intervals

🤔Before reading on: When scanning sorted intervals, do you merge only with the last merged interval or with all previous merged intervals? Commit to your answer.

Concept: Use a loop to merge intervals one by one after sorting.

Start with the first interval as merged. For each next interval, compare it with the last merged interval. If they overlap, merge them. Otherwise, add the new interval to the merged list. This way, you only compare with the last merged interval.

Result

A list of merged intervals with no overlaps.

This approach is efficient because it avoids repeated comparisons and uses the sorted order.

5

Intermediate

Handling Edge Cases in Merging

🤔Before reading on: If two intervals just touch at a point, like [1,2] and [2,3], should they be merged? Commit to your answer.

Concept: Decide if touching intervals count as overlapping and handle empty or single intervals.

Intervals that touch at a point (end of one equals start of another) are usually merged to form a continuous interval. Also, handle cases where input is empty or has one interval by returning it as is.

Result

Correct merging behavior even in special cases.

Handling edge cases prevents bugs and ensures the algorithm works for all inputs.

6

Advanced

Implementing Merge Overlapping Intervals in C

🤔Before reading on: How would you store and return merged intervals in C, given no built-in dynamic arrays? Commit to your answer.

Concept: Write a complete C function to merge intervals using arrays and pointers.

Use a struct to represent intervals. Sort intervals using qsort. Iterate and merge intervals, storing results in a separate array. Return the merged intervals and their count via pointers. Handle memory carefully.

Result

A working C function that merges intervals and returns the merged list.

Implementing in C teaches memory management and careful data handling for real-world use.

7

Expert

Optimizing and Extending Merge Intervals

🤔Before reading on: Can merge overlapping intervals be done faster than O(n log n)? Commit to your answer.

Concept: Explore algorithmic limits, in-place merging, and extensions like merging intervals with extra data.

Sorting takes O(n log n), which is optimal for arbitrary intervals. In-place merging can save memory but requires careful shifting. Extensions include merging intervals with associated values or multi-dimensional intervals, which add complexity.

Result

Understanding performance limits and practical extensions.

Knowing limits and extensions prepares you for advanced problems and optimizations.

Under the Hood

The algorithm first sorts intervals by their start time to line them up. Then it scans from left to right, keeping track of the last merged interval. If the current interval overlaps or touches the last merged one, it updates the end of the last merged interval to cover both. Otherwise, it adds the current interval as a new merged interval. This works because sorting guarantees all overlaps are adjacent or close.

Why designed this way?

Sorting simplifies the problem by ordering intervals so overlaps appear consecutively. Without sorting, checking all pairs would be inefficient (O(n²)). The linear scan after sorting reduces complexity to O(n log n) due to sorting. This design balances simplicity, efficiency, and ease of implementation.

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

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

Merge process:
Start with [1,3]
Compare with [2,6]: overlap -> merge to [1,6]
Compare with [8,10]: no overlap -> add [8,10]
Compare with [15,18]: no overlap -> add [15,18]

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

Myth Busters - 4 Common Misconceptions

Quick: If intervals [1,4] and [4,5] touch at a point, do they merge? Commit yes or no.

Common Belief: Intervals that only touch at a single point are not overlapping and should stay separate.

Reality: Intervals touching at a point are usually merged to form a continuous interval without gaps.

Why it matters: Not merging touching intervals can cause unnecessary fragmentation and incorrect results in scheduling or range queries.

Quick: Is sorting intervals by end time enough to merge them correctly? Commit yes or no.

Common Belief: Sorting intervals by their end time is enough to merge overlapping intervals correctly.

Reality: Sorting must be done by start time to ensure correct merging order and avoid missing overlaps.

Why it matters: Sorting by end time can cause missed merges and incorrect final intervals.

Quick: Can you merge intervals by checking all pairs without sorting efficiently? Commit yes or no.

Common Belief: You can merge intervals efficiently by checking all pairs without sorting.

Reality: Checking all pairs without sorting leads to O(n²) time, which is inefficient for large inputs.

Why it matters: Ignoring sorting leads to slow algorithms that don't scale well.

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

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

Reality: Sometimes intervals do not overlap, so the number of intervals stays the same after merging.

Why it matters: Expecting fewer intervals always can cause wrong assumptions about output size and memory.

Expert Zone

1

Merging intervals in-place requires careful shifting of array elements to avoid overwriting data.

2

When intervals have extra data (like labels), merging must decide how to combine or preserve that data.

3

Floating point intervals or multi-dimensional intervals require more complex overlap checks and merging logic.

When NOT to use

If intervals are already sorted and non-overlapping, merging is unnecessary. For dynamic interval sets with frequent insertions and queries, interval trees or segment trees are better alternatives.

Production Patterns

Used in calendar apps to merge busy times, in database query optimizers to combine ranges, and in network systems to merge IP address ranges for routing.

Connections

Interval Trees

Builds-on

Understanding merging intervals helps grasp interval trees, which efficiently manage dynamic intervals and queries.

Sorting Algorithms

Depends on

Efficient merging relies on sorting intervals first, showing the importance of sorting as a foundational tool.

Project Management Scheduling

Application

Merging overlapping intervals models combining overlapping tasks or meetings, improving resource allocation and planning.

Common Pitfalls

#1 Not sorting intervals before merging.

Wrong approach:

void mergeIntervals(int intervals[][2], int n) {
// No sorting
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (intervals[i][1] >= intervals[j][0]) {
// merge logic
}
}
}
}

Correct approach:

qsort(intervals, n, sizeof(intervals[0]), compareStart);
// Then merge in one pass

Root cause:

Assuming intervals are already ordered or that sorting is unnecessary leads to incorrect merges and inefficient code.

#2 Merging intervals incorrectly by only updating start or end without checking both.

Wrong approach:

if (intervals[i][1] >= intervals[j][0]) {
intervals[i][1] = intervals[j][1]; // blindly overwrite end
}

Correct approach:

if (intervals[i][1] >= intervals[j][0]) {
intervals[i][1] = intervals[i][1] > intervals[j][1] ? intervals[i][1] : intervals[j][1];
}

Root cause:

Not comparing ends properly causes loss of interval coverage and wrong merges.

#3 Not handling intervals that just touch at endpoints as overlapping.

Wrong approach:

if (intervals[i][1] > intervals[j][0]) {
// merge
}

Correct approach:

if (intervals[i][1] >= intervals[j][0]) {
// merge
}

Root cause:

Using strict greater than misses intervals that meet exactly at endpoints.

Key Takeaways

Merging overlapping intervals simplifies multiple overlapping ranges into fewer continuous intervals.

Sorting intervals by their start time is essential for efficient and correct merging.

Merging is done by comparing each interval with the last merged interval and combining if they overlap or touch.

Edge cases like touching intervals and empty inputs must be handled carefully to avoid bugs.

Understanding merging intervals is foundational for advanced data structures like interval trees and practical applications like scheduling.