Merge Overlapping Intervals in DSA Java - Execution Trace

Concept Flow - Merge Overlapping Intervals

Sort intervals by start

↓

Initialize merged list empty

↓

For each interval

↓

Check overlap with last merged

↓

Merge intervals

↓

Repeat

↓

Done

Sort intervals first, then go through each interval to merge if overlapping or add if not.

Execution Sample

DSA Java

int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
  if (merged.isEmpty() || merged.get(merged.size()-1)[1] < interval[0]) {
    merged.add(new int[]{interval[0], interval[1]});
  } else {
    merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], interval[1]);
  }
}

Sort intervals by start, then merge overlapping intervals into a new list.

Execution Table

Step	Operation	Current Interval	Last Merged Interval	Action	Merged List State
1	Sort intervals	N/A	N/A	Intervals sorted	[]
2	Process interval	[1,3]	N/A	Merged list empty, add interval	[[1,3]]
3	Process interval	[2,6]	[1,3]	Overlap detected, merge to [1,6]	[[1,6]]
4	Process interval	[8,10]	[1,6]	No overlap, add interval	[[1,6],[8,10]]
5	Process interval	[15,18]	[8,10]	No overlap, add interval	[[1,6],[8,10],[15,18]]
6	End	N/A	N/A	All intervals processed	[[1,6],[8,10],[15,18]]

💡 All intervals processed and merged where overlapping.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
intervals	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]
merged	[]	[[1,3]]	[[1,6]]	[[1,6],[8,10]]	[[1,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]
current interval	N/A	[1,3]	[2,6]	[8,10]	[15,18]	N/A
last merged interval	N/A	[1,3]	[1,6]	[8,10]	[15,18]	N/A

Key Moments - 3 Insights

Why do we sort intervals before merging?

Sorting ensures intervals are in order by start time, so overlapping intervals come one after another. See Step 1 in execution_table where sorting happens first.

How do we know if two intervals overlap?

We check if the start of the current interval is less than or equal to the end of the last merged interval. In Step 3, [2,6] overlaps with [1,3] because 2 ≤ 3.

What happens if intervals do not overlap?

We add the current interval as a new separate interval in merged list. See Steps 4 and 5 where intervals [8,10] and [15,18] are added without merging.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the merged list state after merging?

A [[1,6]]

B [[2,6]]

C [[1,3],[2,6]]

D [[1,3]]

💡 Hint

Check the 'Merged List State' column at Step 3 in execution_table.

At which step does the condition for no overlap occur?

A Step 2

B Step 3

C Step 4

D Step 1

💡 Hint

Look for 'No overlap' in the 'Action' column in execution_table.

If the intervals were not sorted first, what would happen to the merging process?

A Merging would still work correctly.

B Some overlapping intervals might not merge properly.

C The merged list would be empty.

D The code would crash.

💡 Hint

Refer to Step 1 in execution_table where sorting is done before merging.

Concept Snapshot

Merge Overlapping Intervals:
1. Sort intervals by start time.
2. Initialize empty merged list.
3. For each interval:
   - If no overlap with last merged, add it.
   - Else merge by updating end time.
4. Result is merged intervals without overlaps.

Full Transcript

To merge overlapping intervals, first sort all intervals by their start times. Then create an empty list to hold merged intervals. Go through each interval one by one. If the merged list is empty or the current interval does not overlap with the last merged interval, add it to the merged list. If it overlaps, merge by updating the end time of the last merged interval to the maximum end time between the two. Continue until all intervals are processed. The final merged list contains intervals with no overlaps.

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