Merge Overlapping Intervals in DSA Java

Mental Model

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

Analogy: Imagine you have several time slots booked for meetings. If two meetings overlap or touch, you merge them into one longer meeting to avoid confusion.

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 overlaps

Step 1: Sort intervals by start time

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

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

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

merged: [1,3]

Why: We need a base interval to compare others against

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

merged: [1,6]

Why: Since 2 <= 3, intervals overlap, so merge by extending end to max(3,6)=6

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

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

Why: 8 > 6 means no overlap, so add new interval

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

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

Why: 15 > 10 means no overlap, add new interval

Result:

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

Annotated Code

DSA Java

import java.util.*;

class Interval {
    int start, end;
    Interval(int s, int e) { start = s; end = e; }
    public String toString() { return "[" + start + "," + end + "]"; }
}

public class MergeIntervals {
    public static List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() <= 1) return intervals;

        // Sort intervals by start time
        intervals.sort(Comparator.comparingInt(i -> i.start));

        List<Interval> merged = new ArrayList<>();
        Interval last = intervals.get(0);
        merged.add(last);

        for (int i = 1; i < intervals.size(); i++) {
            Interval current = intervals.get(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
                last = current;
                merged.add(last);
            }
        }
        return merged;
    }

    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
            new Interval(1,3), new Interval(2,6), new Interval(8,10), new Interval(15,18)
        );
        List<Interval> merged = merge(intervals);
        for (Interval interval : merged) {
            System.out.print(interval + " ");
        }
        System.out.println();
    }
}

intervals.sort(Comparator.comparingInt(i -> i.start));

Sort intervals by their start time to process in order

Interval last = intervals.get(0); merged.add(last);

Initialize merged list with first interval as base

if (current.start <= last.end) { last.end = Math.max(last.end, current.end); }

If intervals overlap, merge by extending the end of last interval

else { last = current; merged.add(last); }

If no overlap, add current interval as new merged interval

Output

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

Complexity Analysis

Time: O(n log n) because sorting the intervals takes O(n log n) and merging takes O(n)

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

vs Alternative: Naive approach compares every interval with every other, leading to O(n^2) time, so sorting + one pass merge is more efficient

Edge Cases

empty list

returns empty list immediately

DSA Java

if (intervals.size() <= 1) return intervals;

single interval

returns the same single interval without changes

DSA Java

if (intervals.size() <= 1) return intervals;

all intervals overlapping

merges all into one big interval

DSA Java

if (current.start <= last.end) { last.end = Math.max(last.end, current.end); }

When to Use This Pattern

When you see a list of ranges or intervals and need to combine overlapping parts, reach for the merge intervals pattern because sorting and merging in one pass is efficient and clean.

Common Mistakes

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

Mistake: Creating new intervals instead of updating existing merged interval
Fix: Update the end of the last merged interval to extend it instead of adding new intervals unnecessarily

Summary

Merges overlapping intervals into combined intervals without overlaps.

Use when you have multiple intervals and want to simplify them by merging overlaps.

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

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