Understanding Merge Intervals in Java

What We're Solving & Scheduling Constraints

Consolidating overlapping intervals is a classic algorithmic challenge frequently asked during technical screens. The Merge Intervals problem provides us with a collection of numerical intervals, where each intervals[i] = [starti, endi]. The task is to identify and combine any overlapping ranges, returning an array of non-overlapping intervals that cover the entire span of the input.

For example, if the input is [[1, 3], [2, 6], [8, 10], [15, 18]]:

• Overlap Check: The first two intervals, [1, 3] and [2, 6], share a boundary overlap because the start of the second interval (2) is less than or equal to the end of the first interval (3). We merge them into a single consolidated interval: [1, 6].
• No Overlap: The interval [8, 10] does not share any overlap with either [1, 6] or [15, 18].
• Merged Result: The final output is [[1, 6], [8, 10], [15, 18]].

This problem is a vital building block in several real-world contexts:

• Calendar & Booking Software: Consolidating overlapping meetings or reservations to represent free and busy blocks.
• Compiler Design: Optimizing memory register allocations by finding the active lifespans of variables.
• Database Query Optimizers: Merging separate query ranges into single consolidated scans to minimize disk reads.

The Approach

Sorting & Greedy Merging (O(n log n) Time, O(n) Space)

The core strategy relies on sorting the array of intervals by their starting values (O(n log n) time complexity). By arranging the list chronologically, we guarantee that if any interval overlaps with preceding intervals, it must overlap with the one directly preceding it.

1. Chronological Sort: We sort the intervals based on start time: Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])).
2. Iterative Scan: We maintain a tracking window, called activeInterval, initialized to the first sorted interval. We then traverse the remaining list:
   • Merge Condition: If the current interval's start value is less than or equal to the active interval's end value, they overlap. We merge them by setting the active interval's end value to the maximum of the two: activeInterval[1] = Math.max(activeInterval[1], current[1]).
   • Split Condition: If the current interval's start value is strictly greater than the active interval's end value, there is a gap. We add the active interval to our results list and update activeInterval to point to the current interval.
3. Capture Final State: Once the loop completes, we append the final activeInterval to our output collection.

Sorting dominates the time complexity at O(n log n), while the merge loop runs in linear O(n) time.

Detailed Trace Walkthrough

Let's trace this logic step-by-step using the input array intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]:

1. Step 1 (Sorting): Sort intervals by their start values:
   • Sorted list: [[1, 3], [2, 6], [8, 10], [15, 18]].
2. Step 2 (Initialize):
   • We assign activeInterval = [1, 3] and create an empty result list.
3. Step 3 (First Loop Item: [2, 6]):
   • We compare start values: 2 is less than or equal to the active end value 3.
   • Overlap detected! We merge by updating the active end value: activeInterval[1] = Math.max(3, 6) = 6.
   • Active interval is now [1, 6].
4. Step 4 (Second Loop Item: [8, 10]):
   • We compare start values: 8 is strictly greater than the active end value 6.
   • No overlap! We save the active interval [1, 6] to our result list: result = [[1, 6]].
   • Update our active tracker: activeInterval = [8, 10].
5. Step 5 (Third Loop Item: [15, 18]):
   • We compare start values: 15 is strictly greater than the active end value 10.
   • No overlap! We save the active interval [8, 10] to our result list: result = [[1, 6], [8, 10]].
   • Update our active tracker: activeInterval = [15, 18].
6. Step 6 (Loop Termination):
   • The loop ends. We append our final active tracker [15, 18] to our result list: result = [[1, 6], [8, 10], [15, 18]].
7. Step 7 (Final Output): We convert our list into a 2D array and return it.

Code Breakdown

Low-level implementation highlights of our Java solution:

• Integer.compare(a[0], b[0]) avoids integer subtraction overflow issues during comparator evaluation.
• mergedList.add(activeInterval) passes object references. Because we modify the active interval arrays in-place (activeInterval[1] = Math.max(...)), the merged list reflects all updates correctly.
• toArray(new int[mergedList.size()][]) converts our dynamic collection back to a raw 2D primitive array.

Java Solution

Below is the complete Java implementation featuring the chronological sorting comparator, along with a main execution runner to print the results.

package io.practise.dsa;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class MergeIntervals {
 
    // Sorting & Greedy Merge: Time O(N log N), Space O(N)
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
 
        // Sort intervals based on their start values
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
 
        List<int[]> mergedList = new ArrayList<>();
        int[] activeInterval = intervals[0];
 
        for (int i = 1; i < intervals.length; i++) {
            int[] current = intervals[i];
 
            // If current interval overlaps with the active one, merge them
            if (activeInterval[1] >= current[0]) {
                activeInterval[1] = Math.max(activeInterval[1], current[1]);
            } else {
                // Otherwise, save the active interval and start tracking the new one
                mergedList.add(activeInterval);
                activeInterval = current;
            }
        }
 
        // Add the last active interval
        mergedList.add(activeInterval);
 
        return mergedList.toArray(new int[mergedList.size()][]);
    }
 
    public static void main(String[] args) {
        MergeIntervals solver = new MergeIntervals();
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
 
        System.out.println("--- Merge Intervals Demonstration ---");
        System.out.println("Input Intervals: " + Arrays.deepToString(intervals));
        int[][] result = solver.merge(intervals);
        System.out.println("Merged Intervals: " + Arrays.deepToString(result)); // Expected: [[1, 6], [8, 10], [15, 18]]
    }
}

Conclusion & Takeaways

The Merge Intervals problem is a perfect demonstration of using sorting to unlock greedy optimizations. By establishing a guaranteed chronological order, we can merge overlapping segments in a single linear pass.