Merge Overlapping Intervals in DSA Java - 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, 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 conflicts. Merging helps simplify and organize these intervals so you can see the true coverage or availability clearly.

Where it fits

Before learning this, you should understand arrays or lists and how to sort them. 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 continuous interval to avoid duplication.

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 overlapping pieces together to make 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]

Diagram:

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

Build-Up - 7 Steps

1

Foundation

Understanding Intervals and Overlaps

Concept: Intervals are pairs of numbers representing a range, and overlapping means two intervals share some common numbers.

An interval is like a segment on a number line, for example [1,3] means all numbers from 1 to 3. Two intervals overlap if they share any number. For example, [1,3] and [2,4] overlap because 2 and 3 are in both.

Result

You can identify if two intervals overlap by checking if the start of one is less than or equal to the end of the other.

Understanding what overlap means is the foundation for merging intervals correctly.

2

Foundation

Sorting Intervals by Start Time

Concept: Sorting intervals by their start time helps to process them in order and easily find overlaps.

Given intervals like [8,10], [1,3], [2,6], sort them by their first number: [1,3], [2,6], [8,10]. This order makes it easier to compare each interval with the previous one to find overlaps.

Result

Sorted intervals: [1,3], [2,6], [8,10]

Sorting is key because it lets you check overlaps by looking only at the current and previous intervals, reducing complexity.

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: When two intervals overlap, merge them by taking the smallest start and the largest end.

For intervals [1,4] and [3,5], since 3 ≤ 4, they overlap. The merged interval starts at min(1,3) = 1 and ends at max(4,5) = 5, so merged is [1,5].

Result

Merged interval: [1,5]

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

4

Intermediate

Iterative Merging of Multiple Intervals

🤔Before reading on: When merging [1,3], [2,6], and [8,10], do you think the first two merge into one or stay separate? Commit to your answer.

Concept: Process intervals one by one in sorted order, merging with the last merged interval if they overlap.

Start with [1,3]. Next is [2,6], which overlaps with [1,3], so merge to [1,6]. Next is [8,10], which does not overlap with [1,6], so add it as is. Result: [1,6], [8,10].

Result

Merged intervals: [1,6], [8,10]

Iterating and merging step-by-step ensures all overlaps are handled without missing any.

5

Intermediate

Handling Edge Cases in Merging

🤔Before reading on: If intervals [1,4] and [4,5] touch at the boundary, should they merge? Commit to your answer.

Concept: Intervals that touch at boundaries (end of one equals start of another) are considered overlapping and should merge.

For [1,4] and [4,5], since 4 equals 4, they merge into [1,5]. This prevents gaps when intervals just touch.

Result

Merged interval: [1,5]

Recognizing touching intervals as overlapping avoids subtle bugs in interval merging.

6

Advanced

Java Implementation of Merge Intervals

🤔Before reading on: Do you think sorting intervals and merging in one pass is efficient? Commit to your answer.

Concept: Implement merging by sorting intervals and iterating once to merge overlaps in Java.

Code: import java.util.*; public class MergeIntervals { public static int[][] merge(int[][] intervals) { if (intervals.length == 0) return new int[0][]; Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); List merged = new ArrayList<>(); int[] current = intervals[0]; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] <= current[1]) { current[1] = Math.max(current[1], intervals[i][1]); } else { merged.add(current); current = intervals[i]; } } merged.add(current); return merged.toArray(new int[merged.size()][]); } public static void main(String[] args) { int[][] intervals = {{1,3},{2,6},{8,10},{15,18}}; int[][] result = merge(intervals); for (int[] interval : result) { System.out.print("[" + interval[0] + "," + interval[1] + "] "); } } } Output: [1,6] [8,10] [15,18]

Result

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

Combining sorting and one-pass merging is efficient and practical for real-world interval problems.

7

Expert

Optimizing and Extending Merge Intervals

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

Concept: Explore optimization limits and extensions like merging intervals with additional data or dynamic updates.

Sorting intervals takes O(n log n). Without sorting, merging is hard because order is unknown. For dynamic intervals, data structures like interval trees or segment trees help update and query merges efficiently. Also, merging intervals with extra info (like labels) requires careful handling to preserve data during merges.

Result

Sorting remains the fastest general approach; advanced data structures handle dynamic or enriched intervals.

Knowing the limits of sorting and when to use advanced structures prepares you for complex interval problems in production.

Under the Hood

Internally, merging intervals relies on sorting to arrange intervals by start time. This order ensures that when iterating, any overlapping intervals appear consecutively. The algorithm compares the current interval with the last merged one, extending the end if they overlap. This avoids checking all pairs, reducing complexity from O(n²) to O(n log n) due to sorting.

Why designed this way?

Sorting first was chosen because it simplifies overlap detection to a linear scan. Alternatives like checking all pairs are inefficient. Data structures like interval trees exist but are more complex and used for dynamic or repeated queries. The design balances simplicity, efficiency, and ease of implementation.

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 [1,6], move to [8,10]
Compare with [15,18]: no overlap -> add [8,10], move to [15,18]
Add last interval [15,18]

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

Myth Busters - 4 Common Misconceptions

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

Common Belief: Intervals must overlap by at least one number to merge; touching at boundaries is not enough.

Reality: Intervals that touch at boundaries (end of one equals start of another) are considered overlapping and should merge.

Why it matters: Not merging touching intervals causes unnecessary splits and incorrect interval counts, leading to bugs in scheduling or coverage calculations.

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

Common Belief: You can merge intervals by checking each pair without sorting.

Reality: Without sorting, you must compare every pair, leading to inefficient O(n²) time. Sorting reduces this to O(n log n) and allows linear merging.

Why it matters: Ignoring sorting leads to slow algorithms that don't scale, causing performance issues in large datasets.

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: If no intervals overlap, merging keeps the same number of intervals.

Why it matters: Expecting fewer intervals can mislead you to think merging always changes data, but sometimes it just confirms no overlaps.

Quick: Is it safe to modify the original intervals array during merging? Commit yes or no.

Common Belief: You can modify the original intervals array directly during merging without issues.

Reality: Modifying the original array can cause bugs if the data is used elsewhere; it's safer to create a new list for merged intervals.

Why it matters: Modifying input data unexpectedly can cause hard-to-find bugs in larger systems.

Expert Zone

1

Merging intervals with additional metadata (like labels or weights) requires careful merging logic to preserve or combine metadata correctly.

2

In streaming or real-time systems, intervals may arrive unordered; using interval trees or balanced trees allows efficient dynamic merging.

3

Edge cases like empty intervals, single-point intervals, or intervals with negative ranges require explicit handling to avoid errors.

When NOT to use

If intervals are dynamic and frequently updated, or you need fast queries on merged intervals, use interval trees or segment trees instead of simple sorting and merging. Also, if intervals carry complex metadata, specialized merging logic or data structures are better.

Production Patterns

In calendar apps, merging overlapping meetings simplifies display and conflict detection. In network systems, merging IP ranges reduces firewall rules. In computational geometry, merging intervals helps in line sweeping algorithms for detecting overlaps.

Connections

Interval Trees

Builds-on

Understanding merging intervals is foundational before learning interval trees, which handle dynamic intervals and queries efficiently.

Sorting Algorithms

Depends-on

Efficient merging relies on sorting intervals first, showing how sorting is a key step in many algorithms.

Project Management Scheduling

Application

Merging overlapping intervals directly applies to scheduling tasks and resources, helping avoid conflicts and optimize timelines.

Common Pitfalls

#1 Not sorting intervals before merging.

Wrong approach:

int[][] intervals = {{8,10},{1,3},{2,6}};
// Attempt to merge without sorting
// This leads to incorrect merges or missed overlaps

Correct approach:

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
// Then merge intervals in sorted order

Root cause:

Without sorting, intervals are unordered, so overlaps may be missed or incorrectly merged.

#2 Ignoring intervals that only touch at boundaries.

Wrong approach:

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

Correct approach:

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

Root cause:

Using strict less than misses intervals that start exactly where the previous ends, causing incorrect splits.

#3 Modifying the input intervals array directly and returning it.

Wrong approach:

return intervals; // after partial modification without creating new list

Correct approach:

Use a new list to store merged intervals and return a new array to avoid side effects.

Root cause:

Modifying input data can cause unexpected bugs if the original data is used elsewhere.

Key Takeaways

Merging overlapping intervals means combining intervals that share or touch ranges into one continuous interval.

Sorting intervals by their start time is essential to efficiently find and merge overlaps in one pass.

Intervals that touch at boundaries should be merged to avoid gaps and ensure correct coverage.

The standard approach runs in O(n log n) time due to sorting, which is optimal for general cases.

Advanced scenarios with dynamic intervals or extra data require specialized data structures like interval trees.

Practice

1. What is the main purpose of merging overlapping intervals in a list of intervals?

easy

A. To combine intervals that overlap into a single continuous interval

B. To sort intervals by their length

C. To remove all intervals that have the same start point

D. To find the interval with the maximum end value

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 reduces multiple overlapping intervals into fewer intervals without overlaps, simplifying the list.

3. Final Answer:

   To combine intervals that overlap into a single continuous interval -> Option A

4. Quick Check:

   Merging = Combine overlaps [OK]

Hint: Merging means joining overlapping intervals into one [OK]

Common Mistakes:

• Thinking merging sorts intervals by length
• Confusing merging with removing duplicates
• Assuming merging finds max end only

2. Which of the following Java code snippets correctly sorts a list of intervals by their start time before merging?

easy

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

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

C. Collections.sort(intervals, (a, b) -> a.end - b.end);

D. intervals.sort((a, b) -> a.length() - b.length());

Solution

1. Step 1: Identify sorting by start time ascending

   We need to sort intervals by their start value in ascending order for merging.

2. Step 2: Check each option

   Collections.sort(intervals, (a, b) -> a.start - b.start); sorts by start ascending correctly. intervals.sort((a, b) -> b.start - a.start); sorts descending. Collections.sort(intervals, (a, b) -> a.end - b.end); sorts by end, not start. intervals.sort((a, b) -> a.length() - b.length()); sorts by length, which is incorrect.

3. Final Answer:

   Collections.sort(intervals, (a, b) -> a.start - b.start); -> Option A

4. Quick Check:

   Sort by start ascending = Collections.sort(intervals, (a, b) -> a.start - b.start); [OK]

Hint: Sort intervals by start ascending before merging [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Sorting in descending order
• Sorting by interval length

3. What is the output of the following Java code that merges overlapping intervals?

List<Interval> intervals = List.of(new Interval(1,3), new Interval(2,6), new Interval(8,10), new Interval(15,18));
List<Interval> merged = mergeIntervals(intervals);
for (Interval i : merged) {
    System.out.print("[" + i.start + "," + i.end + "] ");
}

Assume mergeIntervals merges intervals correctly.

medium

A. [1,3] [2,6] [8,10] [15,18]

B. [1,6] [2,6] [8,10] [15,18]

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

D. [1,3] [8,10] [15,18]

Solution

1. Step 1: Identify overlapping intervals

   Intervals (1,3) and (2,6) overlap, so they merge into (1,6). Others do not overlap.

2. Step 2: List merged intervals

   Merged list is (1,6), (8,10), (15,18).

3. Final Answer:

   [1,6] [8,10] [15,18] -> Option C

4. Quick Check:

   Merged intervals = [1,6] [8,10] [15,18] [OK]

Hint: Merge overlapping intervals by extending end time [OK]

Common Mistakes:

• Not merging overlapping intervals
• Printing original intervals without merge
• Merging incorrectly leaving duplicates

4. Identify the bug in this Java method that merges intervals:

public List<Interval> mergeIntervals(List<Interval> intervals) {
    Collections.sort(intervals, (a, b) -> a.start - b.start);
    List<Interval> merged = new ArrayList<>();
    for (Interval interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1).end < interval.start) {
            merged.add(interval);
        } else {
            merged.get(merged.size() - 1).end = interval.end;
        }
    }
    return merged;
}

medium

A. It sorts intervals by end instead of start

B. It does not update the end to the max of overlapping intervals

C. It adds intervals even if they overlap

D. It returns the original list instead of merged list

Solution

1. Step 1: Check merging logic

   When intervals overlap, the code sets end to interval.end directly, which may be smaller than current end.

2. Step 2: Correct approach

   It should update end to max of current end and interval.end to cover full overlap.

3. Final Answer:

   It does not update the end to the max of overlapping intervals -> Option B

4. Quick Check:

   Update end = max(end, interval.end) needed [OK]

Hint: Update merged end to max of overlapping ends [OK]

Common Mistakes:

• Setting end to interval.end without max check
• Sorting by wrong field
• Adding overlapping intervals separately

5. Given a list of intervals where some intervals are nested inside others, how does the merge overlapping intervals algorithm handle nested intervals like [(1,10), (2,5), (6,9)]? What is the final merged list?

hard

A. [(2,5), (6,9)]

B. [(1,5), (6,9), (10,10)]

C. [(1,5), (6,10)]

D. [(1,10)]

Solution

1. Step 1: Analyze nested intervals

   Intervals (2,5) and (6,9) are fully inside (1,10), so they overlap completely.

2. Step 2: Merge nested intervals

   Merging results in a single interval (1,10) covering all nested intervals.

3. Final Answer:

   [(1,10)] -> Option D

4. Quick Check:

   Nested intervals merge into outer interval [OK]

Hint: Nested intervals merge into the largest containing interval [OK]

Common Mistakes:

• Keeping nested intervals separate
• Splitting outer interval incorrectly
• Ignoring full overlap cases