ArrayProblem 14 of 36

Merge Intervals

Brute Force
Time: O(n²)
Space: O(n)
Optimal
Time: O(n log n)
Space: O(n)

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.

Example:

  • Input: [[1,3], [2,6], [8,10], [15,18]]
  • Output: [[1,6], [8,10], [15,18]]
  • Explanation: Intervals [1,3] and [2,6] overlap, so they are merged into [1,6]

Approach 1: Brute Force

Intuition

Compare each interval with every other interval. If two intervals overlap, merge them and restart the process until no more merges are possible.

Algorithm

  1. For each interval, check if it overlaps with any other
  2. If overlap found, merge them and remove the original intervals
  3. Add the merged interval and restart
  4. Repeat until no overlaps exist
java
import java.util.*;

public class Solution {
    private boolean isOverlapping(int[] a, int[] b) {
        return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
    }
    
    public int[][] mergeBruteForce(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        
        List<int[]> result = new ArrayList<>(Arrays.asList(intervals));
        boolean merged = true;
        
        while (merged) {
            merged = false;
            List<int[]> temp = new ArrayList<>();
            boolean[] used = new boolean[result.size()];
            
            for (int i = 0; i < result.size(); i++) {
                if (used[i]) continue;
                
                int[] current = result.get(i).clone();
                for (int j = i + 1; j < result.size(); j++) {
                    if (used[j]) continue;
                    
                    if (isOverlapping(current, result.get(j))) {
                        current[0] = Math.min(current[0], result.get(j)[0]);
                        current[1] = Math.max(current[1], result.get(j)[1]);
                        used[j] = true;
                        merged = true;
                    }
                }
                temp.add(current);
            }
            result = temp;
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

Complexity Analysis

  • Time Complexity: O(n²) - Comparing each interval with every other
  • Space Complexity: O(n) - Storing the result

Approach 2: Sort and Merge (Optimal)

Intuition

If we sort intervals by their start time, overlapping intervals will be adjacent. We can then merge them in a single pass.

Algorithm

  1. Sort intervals by start time
  2. Initialize result with the first interval
  3. For each subsequent interval:
    • If it overlaps with the last interval in result, merge them
    • Otherwise, add it to result
  4. Two intervals overlap if current.start <= last.end
java
import java.util.*;

public class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][];
        
        // Sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            int[] last = result.get(result.size() - 1);
            
            // If current interval overlaps with last, merge them
            if (intervals[i][0] <= last[1]) {
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                // No overlap, add new interval
                result.add(intervals[i]);
            }
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) - Dominated by sorting
  • Space Complexity: O(n) - For storing the result (O(log n) for sorting)

Key Takeaways

  1. Sorting simplifies overlap detection - Adjacent intervals after sorting can only overlap with each other
  2. Two intervals [a, b] and [c, d] overlap if max(a, c) <= min(b, d)
  3. After sorting by start time, we only need to check: current.start <= previous.end
  4. This is a common pattern: sort first, then single-pass merge
  5. Similar problems: Insert Interval, Meeting Rooms, Non-overlapping Intervals
Previous
Kadanes Algo [V.V.V.V.V IMP]
Next
Next Permutation