Sorting and Merging Intervals in Java

Interval sorting problems are fundamental in algorithm design, requiring careful handling of overlapping ranges and proper ordering strategies for efficient processing in production systems.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are the intervals guaranteed to be non-overlapping, or do we need to handle overlapping intervals?
2. What is the expected size of input intervals? (e.g., up to 10^5 intervals)
3. Can we mutate the input array of intervals, or do we need to preserve it?
4. Should we return a new list or modify the input in-place?
5. What is the target time complexity for follow-up? O(n log n) or better?

Restate the pattern or problem type in your own words: The sorting intervals pattern involves taking a collection of interval objects (typically represented as [start, end] pairs) and organizing them in a way that enables efficient operations like merging overlapping intervals, finding gaps, or performing range queries. This pattern leverages sorting as a foundational step to bring structure to what might otherwise be an unorganized set of ranges.

Clarify the signal words and constraint shape that point to it:

• Signal words: "intervals", "overlapping", "merge", "range", "time slots"
• Constraint shape: Input consists of discrete start-end pairs, often with potential for overlap or adjacency
• Common constraints: intervals can be sorted by start time, end time, or other criteria

Note any assumptions you are making:

• Each interval is represented as a two-element array [start, end] where start ≤ end
• The intervals are discrete ranges on a timeline or number line
• Overlapping intervals can be merged if they share common elements or touch at endpoints

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is primarily designed for static input scenarios where all intervals are available upfront. It's not naturally suited for streaming data where new intervals arrive continuously, though it can be adapted with additional tracking structures. For online scenarios, a more sophisticated data structure like an interval tree or segment tree might be preferred.

The core insight is that sorting intervals by their start times creates a natural ordering that makes overlap detection and merging operations linear in the sorted sequence, reducing complexity from O(n²) to O(n log n).

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Merge overlapping intervals"
• "Given a list of time ranges"
• "Find non-overlapping time slots"
• "Intervals with start and end times"
• "Merge intervals that touch or overlap"

Why this pattern fits better than the most common alternatives: This pattern is specifically suited for problems involving interval manipulation where the key insight is that overlapping intervals can be merged by sorting them first. Unlike graph-based approaches or sliding window techniques, interval merging leverages the inherent ordering property of intervals to reduce complexity from O(n²) to O(n log n). The sorting step allows us to process intervals sequentially and merge only adjacent ones that actually overlap.

Conditions where a variation or related pattern applies instead:

• If the problem asks for counting overlapping intervals rather than merging, use sweep line algorithm or event processing
• If intervals are processed in real-time without knowing all intervals upfront, use streaming interval data structures
• If the problem involves finding gaps between intervals rather than merging them, use gap-finding approaches

The core insight that makes this pattern work: The key insight is that once intervals are sorted by start time, any overlapping intervals will be adjacent in the sorted array. This means we only need to check if the current interval's start time is less than or equal to the previous interval's end time to determine if they overlap. This transforms an O(n²) brute force comparison into an O(n) linear scan after sorting.

The pattern excels when:

1. Input consists of discrete time ranges or intervals
2. Overlap definition is clear (touching at endpoints counts as overlap)
3. The problem asks for a minimal set of non-overlapping intervals that cover the same space as input
4. Input size is manageable for O(n log n) sorting (typically up to 10⁶ elements)

3. Approach Evolution

Interview communication script:

My first instinct is to solve this by sorting the intervals and then merging overlapping ones, because that seems like the most direct approach to the problem. But let me think about the complexity - if I naively compare every interval with every other interval, that would be O(n²) time because for each interval I'd have to check all others. That's not acceptable.

Let me think about how to optimize this. I notice that if I sort the intervals by their start times first, then I can process them sequentially and only need to compare each interval with the previous one to determine if they overlap. This reduces the problem to O(n log n) time due to sorting, and O(n) for the linear scan afterward.

If I maintain the invariant that intervals are processed in order of start time, then when I encounter a new interval, I can simply compare its start time with the end time of my currently building merged interval. If it overlaps, I extend the end time; otherwise, I finalize the current interval and start a new one.

This approach works because once intervals are sorted by start time, any overlapping intervals will be adjacent in the sorted sequence. The key insight is that I don't need to check all previous intervals - just the last one in my current merged result.

Brute-force approach and why it is not ideal:

The brute force approach would be to compare every interval with every other interval to find overlaps. For each interval, I'd iterate through all others and check if they overlap by comparing start and end times. This approach has O(n²) time complexity because for n intervals, I perform n comparisons for each interval. It's inefficient and doesn't scale well with larger inputs.

Improved approach and the key optimization:

The key optimization is to sort intervals by their start times first. Once sorted, overlapping intervals will appear consecutively in the sequence. Then I can iterate through the sorted intervals once, maintaining a current merged interval and extending it when new intervals overlap with it. This reduces the problem to O(n log n) time complexity (dominated by sorting) and O(n) space for the result list.

Final approach with step-by-step reasoning:

1. First, I sort all intervals by their start times to group overlapping intervals together
2. Then I iterate through the sorted intervals, maintaining a current "merged" interval
3. For each new interval, I compare its start time with the end time of my current merged interval:
   • If it overlaps (start ≤ current end), I extend the current interval's end time
   • If it doesn't overlap, I finalize the current merged interval and start a new one
4. After processing all intervals, I add the final merged interval to the result

The key invariant that must hold is that at any point during iteration, all intervals processed so far that should be merged together are properly merged into a single interval.

Important invariants that must hold:

1. The intervals are always processed in order of start time (maintained by sorting)
2. When building a merged interval, its end time is always the maximum end time of all intervals in that group
3. At each step, I only compare with the most recently added interval in my result list to determine overlap
4. The final merged intervals are always in proper order (start time increasing)

4. Data Structure Choice

For the interval sorting problem, I'll use a combination of standard Java collections to achieve an efficient solution.

Primary Data Structures:

1. int[][] intervals - The input array of intervals. This is the primary data structure that holds our problem's input. It's immutable in this context, so we don't need to worry about mutation concerns.

2. List<int[]> result - A dynamic list to collect the merged intervals. This is needed because we don't know the final size of the result beforehand, and ArrayList provides O(1) amortized append operations.

3. PriorityQueue<int[]> - While not strictly necessary for the optimal O(n log n) solution, a priority queue could be used to sort intervals by start time if we wanted to avoid explicit sorting. However, since we're ultimately sorting anyway, direct sorting is more efficient.

Why These Choices Work:

The key insight is that we're solving a classic interval merging problem where:

• We need to process intervals in sorted order by start time
• We want to build a result list incrementally
• The input is static (we don't need streaming support)

The ArrayList for results is optimal because:

• We're building a list of unknown size
• It provides O(1) amortized insertion (better than LinkedList's O(n) insertion)
• It supports efficient iteration

Space Impact:

• Input array is O(n) space (no change)
• Result list is O(k) where k ≤ n (at most n intervals in worst case)
• Sorting in-place is O(log n) space for the sorting algorithm's stack
• Overall space complexity: O(n)

Helper Structure: We don't need any additional helper structures beyond what's standard in Java. The solution uses only built-in collections that are optimized for the operations we need.

This choice balances simplicity with efficiency - no custom data structures or complex wrappers are needed, and standard collections provide the performance characteristics we require.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Consider the input intervals: [[1,3], [2,6], [8,10], [15,18]]

Step 1: Sort intervals by start time After sorting: [[1,3], [2,6], [8,10], [15,18]]

• The intervals are already sorted by start time
• If they weren't, we'd sort by the first element of each interval

Step 2: Initialize result with first interval Result list: [[1,3]]

• We start with the first interval as our initial "merged" interval

Step 3: Process remaining intervals For each subsequent interval, we check if it overlaps with the last merged interval:

Interval [2,6]:

• Compare start time (2) with last merged interval's end time (3)
• Since 2 ≤ 3, they overlap
• Update the last merged interval to [1, max(3,6)] = [1,6]
• Result: [[1,6]]

Interval [8,10]:

• Compare start time (8) with last merged interval's end time (6)
• Since 8 > 6, no overlap
• Add [8,10] to result as new interval
• Result: [[1,6], [8,10]]

Interval [15,18]:

• Compare start time (15) with last merged interval's end time (10)
• Since 15 > 10, no overlap
• Add [15,18] to result as new interval
• Result: [[1,6], [8,10], [15,18]]

Final result: [[1,6], [8,10], [15,18]]

The key insight is that after sorting, we can process intervals sequentially and merge overlapping ones by comparing the start time of current interval with end time of previously merged interval. This works because any overlapping intervals must be adjacent in the sorted sequence.

Edge cases handled:

• Single interval: Returns same interval
• No overlaps: All intervals remain separate
• Multiple overlaps: Properly merges all connected overlapping intervals

6. Java Solution

import java.util.*;

public class IntervalMerger {
    
    /**
     * Merges overlapping intervals in-place and returns the merged result.
     * Assumes input intervals are sorted by start time.
     * 
     * @param intervals 2D array of intervals where each interval is [start, end]
     * @return Merged intervals as 2D array
     */
    public int[][] merge(int[][] intervals) {
        // Handle edge cases
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
        
        // Sort intervals by start time - O(n log n)
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // Use list to collect merged intervals
        List<int[]> result = new ArrayList<>();
        
        // Process each interval
        for (int i = 0; i < intervals.length; i++) {
            int[] current = intervals[i];
            
            // If result is empty or no overlap with last interval
            if (result.isEmpty() || result.get(result.size() - 1)[1] < current[0]) {
                result.add(current);
            } else {
                // Overlap exists - merge by extending end time
                int[] last = result.get(result.size() - 1);
                last[1] = Math.max(last[1], current[1]);
            }
        }
        
        // Convert list back to array
        return result.toArray(new int[result.size()][]);
    }
    
    /**
     * Alternative approach that does not mutate input array
     * Creates a copy before sorting to preserve original data.
     */
    public int[][] mergeWithCopy(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
        
        // Create copy to avoid mutating input
        int[][] copy = new int[intervals.length][2];
        for (int i = 0; i < intervals.length; i++) {
            copy[i] = Arrays.copyOf(intervals[i], 2);
        }
        
        // Sort the copy
        Arrays.sort(copy, (a, b) -> a[0] - b[0]);
        
        List<int[]> result = new ArrayList<>();
        
        for (int i = 0; i < copy.length; i++) {
            int[] current = copy[i];
            
            if (result.isEmpty() || result.get(result.size() - 1)[1] < current[0]) {
                result.add(current);
            } else {
                int[] last = result.get(result.size() - 1);
                last[1] = Math.max(last[1], current[1]);
            }
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

The solution uses a greedy approach with sorting to efficiently merge overlapping intervals. It processes intervals in order of start time and maintains a result list where each new interval either gets added (no overlap) or merges with the last interval in the result (overlap exists). The key insight is that once sorted, we only need to compare each interval with the most recently added one in our result.

7. Complexity Analysis

Time Complexity: O(n log n)

The dominant cost comes from sorting the intervals, which takes O(n log n) time where n is the number of intervals. The subsequent merging step takes O(n) linear time, making the overall time complexity O(n log n).

Space Complexity: O(1)

If we don't count the space required for the output array, the algorithm uses only constant extra space. We only maintain a few variables (currentStart, currentEnd, result list) regardless of input size. The sorting operation may use O(log n) space on the call stack depending on the sorting implementation, but this is typically considered part of the algorithm's overhead rather than additional space usage.

Why These Bounds Are Correct

The O(n log n) time bound is optimal for this problem because any algorithm that needs to process all intervals and determine their merge relationships must at least examine each interval once, and the sorting step is necessary to properly order intervals for merging. The space complexity is optimal since we only need to store the result set and a constant number of working variables.

Optimality

This solution is optimal in both time and space complexity for the interval merging problem. Since we must examine each interval at least once and the sorting step is unavoidable for proper merging, O(n log n) time and O(1) space represent the theoretical lower bounds for this problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty input: Handle gracefully with empty result list
• Single interval: Should return the interval as-is without any merging
• Two intervals with no overlap: Both should be returned separately

Duplicate Values and Repeated States

• Identical intervals: Should be handled properly (e.g., [1,3], [1,3] should not merge)
• Overlapping intervals with same endpoints: Need to ensure proper merging logic handles edge cases like [1,4], [2,3] where one endpoint touches another
• Intervals that are touching at endpoints: [1,3], [3,5] should merge to [1,5]

Boundary Conditions

• Zero-length intervals: [1,1], [2,2] should be handled correctly
• Negative numbers: Ensure sorting works properly with negative coordinate values
• Large integer values: Verify that interval endpoints don't overflow during arithmetic operations

Common Implementation Mistakes

• Incorrect sorting: Using wrong comparator or not sorting by start time first
• Off-by-one errors in merging logic: When checking if intervals can be merged, ensure proper boundary condition (end1 >= start2)
• Not handling edge case of single interval: Code that assumes at least two intervals
• Modifying input array during iteration: This can cause index shifting issues or incorrect behavior
• Incorrect merging condition: Using end1 > start2 instead of end1 >= start2 which misses touching intervals

Additional Considerations

• Integer overflow: When computing merged interval bounds, ensure operations don't exceed integer limits (though less likely in typical constraints)
• Null intervals: If input contains null values, proper validation should be added
• Unsorted input: Algorithm assumes sorted intervals but problem may not guarantee this, requiring preprocessing

9. Alternative Approaches

There are several alternative approaches to solving the interval sorting problem, each with different trade-offs:

1. Brute Force with Manual Merging Instead of sorting, we could repeatedly scan through intervals to find overlapping ones and merge them. This approach would be O(n²) time complexity in the worst case, as we might need to merge intervals multiple times. It's inefficient but can work for very small inputs.

2. Priority Queue Approach We could use a min-heap to process intervals by their start times, but this doesn't fundamentally improve the complexity since we still need to merge overlapping intervals. The heap would help with ordering but wouldn't reduce the overall merging cost.

3. Two-Pointer Technique on Unsorted Input If we're given unsorted intervals and need to merge them, we could sort first using a custom comparator, then apply the two-pointer technique. This is essentially the same as our main approach but with an explicit sorting step.

4. Divide and Conquer We could recursively divide intervals into halves, sort and merge each half, then merge the results. This would maintain O(n log n) complexity but adds recursive overhead and is more complex to implement correctly.

5. Bucket Sort for Limited Range If the interval values are bounded and small, we could use bucket sort to achieve O(n) time complexity. However, this is only viable when the range of values is significantly smaller than n, which is rarely the case in general interval problems.

Our chosen approach of sorting followed by linear merging is optimal for the general case because it's clean, readable, and achieves the theoretical minimum O(n log n) time complexity for comparison-based sorting. The alternatives either don't improve on this bound or add unnecessary complexity for the general problem space.

10. Test Cases

public class IntervalTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic overlapping intervals
        int[][] intervals1 = {{1,3}, {2,6}, {8,10}, {15,18}};
        // Expected: [[1,6], [8,10], [15,18]]
        
        // Test case 2: Identical intervals
        int[][] intervals2 = {{1,4}, {4,5}};
        // Expected: [[1,5]]
        
        // Test case 3: Empty input
        int[][] intervals3 = {};
        // Expected: []
        
        // Test case 4: Single interval
        int[][] intervals4 = {{1,3}};
        // Expected: [[1,3]]
        
        // Test case 5: All intervals overlapping
        int[][] intervals5 = {{1,4}, {2,3}, {3,5}};
        // Expected: [[1,5]]
        
        // Test case 6: Non-overlapping intervals
        int[][] intervals6 = {{1,2}, {3,4}, {5,6}};
        // Expected: [[1,2], [3,4], [5,6]]
        
        // Test case 7: Complex overlapping
        int[][] intervals7 = {{1,3}, {2,4}, {5,7}, {6,8}, {9,10}};
        // Expected: [[1,4], [5,8], [9,10]]
    }
}

Sample Test Cases:

Basic overlapping intervals: [[1,3], [2,6], [8,10], [15,18]] → [[1,6], [8,10], [15,18]]

• Tests the core merging logic with multiple overlapping ranges

Identical adjacent intervals: [[1,4], [4,5]] → [[1,5]]

• Tests boundary condition where intervals touch but don't overlap

Edge case - empty input: [] → []

• Validates handling of null/empty collections

Edge case - single interval: [[1,3]] → [[1,3]]

• Validates minimal input handling

Complex overlapping: [[1,4], [2,3], [3,5]] → [[1,5]]

• Tests multiple overlapping conditions in one pass

Non-overlapping intervals: [[1,2], [3,4], [5,6]] → [[1,2], [3,4], [5,6]]

• Validates that non-overlapping intervals remain separate

The test cases cover the essential scenarios: basic merging, edge conditions, boundary cases, and various overlap patterns that could break a naive implementation.

11. Final Summary

The core idea is to efficiently merge overlapping intervals by first sorting them and then iterating through the sorted list to identify and combine overlapping ranges. This approach works because once intervals are sorted by start time, any overlapping intervals will be adjacent in the sorted array, making the merge operation straightforward. The solution is optimal with O(n log n) time complexity due to sorting, which is necessary for correctness since we need to process intervals in order to detect overlaps, and O(n) space complexity for the result list. The key insight that makes this efficient is recognizing that sorting eliminates the need for complex data structures or multiple passes through the input.