DSA 450 Notes

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 intervals in the input.

Example:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap, merge into [1,6]

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] are considered overlapping

Approach 1: Brute Force

Intuition

Compare each interval with every other interval. If they overlap, merge them and start over. Continue until no more merges are possible.

Algorithm

For each pair of intervals, check if they overlap
If overlap found, merge them and restart
Continue until no overlaps remain

java

import java.util.*;

public class MergeIntervals {
    public static int[][] mergeIntervalsBruteForce(int[][] intervals) {
        if (intervals.length == 0) return new int[0][];
        
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            result.add(interval.clone());
        }
        
        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;
                    
                    int[] other = result.get(j);
                    if (current[0] <= other[1] && other[0] <= current[1]) {
                        current[0] = Math.min(current[0], other[0]);
                        current[1] = Math.max(current[1], other[1]);
                        used[j] = true;
                        merged = true;
                    }
                }
                
                temp.add(current);
            }
            
            result = temp;
        }
        
        return result.toArray(new int[0][]);
    }
}

Complexity Analysis

Time Complexity: O(n^2) - comparing each pair multiple times
Space Complexity: O(n) - for storing results

Approach 2: Sort and Merge (Optimal)

Intuition

If intervals are sorted by start time, we only need to check if the current interval overlaps with the last merged interval. If it does, extend the last interval; otherwise, add current as a new interval.

Algorithm

Sort intervals by start time
Initialize result with first interval
For each subsequent interval:
- If it overlaps with last interval in result, merge them
- Otherwise, add it as a new interval

java

import java.util.*;

public class MergeIntervals {
    public static int[][] mergeIntervals(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
            if (intervals[i][0] <= last[1]) {
                // Merge: extend the end time
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                // No overlap: add as new interval
                result.add(intervals[i]);
            }
        }
        
        return result.toArray(new int[0][]);
    }
    
    // Using Stack
    public static int[][] mergeIntervalsStack(int[][] intervals) {
        if (intervals.length == 0) return new int[0][];
        
        // Sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        Stack<int[]> stack = new Stack<>();
        stack.push(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            int[] top = stack.peek();
            
            // If current interval overlaps with stack top
            if (intervals[i][0] <= top[1]) {
                // Merge: update the end time
                stack.pop();
                stack.push(new int[]{top[0], Math.max(top[1], intervals[i][1])});
            } else {
                // No overlap: push current interval
                stack.push(intervals[i]);
            }
        }
        
        // Convert stack to array
        int[][] result = new int[stack.size()][];
        for (int i = stack.size() - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] result = mergeIntervals(intervals);
        
        System.out.print("Merged intervals: ");
        for (int[] interval : result) {
            System.out.print("[" + interval[0] + "," + interval[1] + "] ");
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n log n) - dominated by sorting
Space Complexity: O(n) - for storing results (O(log n) for sorting)

Key Takeaways

Sorting simplifies the problem - after sorting, only consecutive intervals can overlap
Two intervals [a,b] and [c,d] overlap if a <= d AND c <= b
After sorting by start: intervals overlap if current.start <= previous.end
Stack can be used but a simple list/vector works just as well
Edge case: touching intervals [1,4] and [4,5] are typically considered overlapping
This is a classic greedy algorithm problem

Merge Overlapping Intervals

Problem Statement

Approach 1: Brute Force

Intuition

Algorithm

Complexity Analysis

Approach 2: Sort and Merge (Optimal)

Intuition

Algorithm

Complexity Analysis

Key Takeaways