Merge Overlapping Intervals in DSA Java - Build from Scratch

Merge Overlapping Intervals

📖 Scenario: You are working on a calendar app that needs to combine overlapping meeting times into one continuous time slot. This helps users see their free time clearly.

🎯 Goal: Build a Java program that merges overlapping intervals from a list of meeting times.

📋 What You'll Learn

Create an array of integer arrays representing intervals

Add a variable to store the merged intervals

Write logic to merge overlapping intervals

Print the merged intervals in the format [start, end]

💡 Why This Matters

🌍 Real World

Merging intervals is useful in calendar apps, booking systems, and timeline visualizations to avoid overlapping events.

💼 Career

Understanding interval merging is important for software engineers working on scheduling, data processing, and optimization problems.

1

Create the intervals array

Create a 2D integer array called intervals with these exact values: {{1, 3}, {2, 6}, {8, 10}, {15, 18}}

DSA Java

// Your code here

Hint

Use int[][] intervals = {{...}, {...}}; to create the array.

2

Create a list to hold merged intervals

Create a variable called merged of type List and initialize it as a new ArrayList<>()

DSA Java

int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
// Your code here

Hint

Use List<int[]> merged = new ArrayList<>(); to create the list.

3

Write logic to merge overlapping intervals

Sort the intervals array by the start time using Arrays.sort(intervals, (a, b) -> a[0] - b[0]). Then use a for loop with variable interval to iterate over intervals. Inside the loop, if merged is empty or the end of the last interval in merged is less than the start of interval, add interval to merged. Otherwise, update the end of the last interval in merged to the maximum of its current end and interval[1].

DSA Java

import java.util.*;

int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
List merged = new ArrayList();
// Your code here

Hint

Sort first, then check if current interval overlaps with last merged interval.

4

Print the merged intervals

Use a for loop with variable interval to iterate over merged. Inside the loop, print each interval in the format [start, end] using System.out.print("[" + interval[0] + ", " + interval[1] + "] "). After the loop, print a newline with System.out.println().

DSA Java

import java.util.*;

int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
List merged = new ArrayList();

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int[] interval : intervals) {
    if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
        merged.add(interval);
    } else {
        merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
    }
}
// Your code here

Hint

Print each merged interval with brackets and a space, then print a newline.

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