2. Merge Intervals

Description

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

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

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

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Approach

• Make sure it is sorted by start time
• we start with current and then check if its last is in between interval of next if yes then maximum of the current end and next end and so the interval would be merged
• If not just simply add them in the result
• ⏱ Time Complexity: O(n log n)
  Why?
  Sorting the intervals takes O(n log n)
  The single pass through the sorted intervals to merge them is O(n)
  Total: O(n log n + n) → simplified to O(n log n)
• 🧠 Space Complexity: O(n)
  Why?
  We use an output List<int[]> to store merged intervals → at worst, we store all n intervals (if none merge)
  Sorting uses constant extra space (since Arrays.sort on primitives is in-place)
  So overall: O(n) due to the result list

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
        List<int[]> ans = new ArrayList<>();
        int[] curr = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (curr[1] >= intervals[i][0]) {
                //merge
                curr[1] = Math.max(curr[1], intervals[i][1]);
            } else {
                ans.add(curr);
                curr = intervals[i];
            }
        }
        //add the last one
        ans.add(curr);
 
        return ans.toArray(new int[ans.size()][]);
    }
}

Optimal Approach: The Local State Machine Algorithm

Code Implementation

import java.util.*;
 
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
 
        // 1. Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
 
        List<int[]> ans = new ArrayList<>();
        int[] curr = intervals[0];
 
        // 2. Single pass starting from index 1
        for (int i = 1; i < intervals.length; i++) {
            if (curr[1] >= intervals[i][0]) {
                // Overlap: stretch current boundary locally
                curr[1] = Math.max(curr[1], intervals[i][1]);
            } else {
                // Gap: commit finished interval and shift curr to the new one
                ans.add(curr);
                curr = intervals[i];
            }
        }
 
        // 3. Flush the last active interval
        ans.add(curr);
 
        return ans.toArray(new int[ans.size()][]);
    }
}
 

//Better intuitive with next being used
import java.util.*;
 
class Solution {
    public int[][] merge(int[][] intervals) {
       //Not required really
       //if (intervals.length <= 1) return intervals;
 
        // 1. Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
 
        List<int[]> ans = new ArrayList<>();
        int[] curr = intervals[0];
 
        // 2. Stream through meetings with overlap-first logic
        for (int[] next : intervals) {
            if (curr[1] >= next[0]) {
                // OVERLAP: curr reaches into/beyond next start -> stretch end boundary
                curr[1] = Math.max(curr[1], next[1]);
            } else {
                // GAP: curr can't reach next -> commit finished interval & start new active one
                ans.add(curr);
                curr = next;
            }
        }
 
        // 3. Flush the final active interval
        ans.add(curr);
 
        return ans.toArray(new int[ans.size()][]);
    }
}

Complexity Analysis

• Time Complexity: $O(N\log N)$ for sorting + $O(N)$ linear scan = $O(N\log N)$ total.
• Space Complexity: $O(N)$ for output list storage.

The Mental Trick (How to Remember It Easily)

Think of the intervals as calendar meetings sorted by start time. To merge them efficiently:

1. Maintain a local pointer (curr) as your active window for the current merged meeting.
2. If the next meeting overlaps (curr[1] >= next[0]), stretch the end boundary locally.
3. If there is a gap, commit curr to your result list and shift curr to the new meeting. Flush the last meeting after the loop!

---

Step-by-Step Example: [[1, 3], [2, 6], [8, 10], [15, 18]]

Step 1: Sort & Initialize (curr)

Sort intervals by start time. Set curr = intervals[0] ([1, 3]). Start loop from index i = 1.

• ans = []
• curr = [1, 3]

Step 2: Single-Pass Scan (i = 1 to N - 1)

• i = 1 ([2, 6]): Check overlap $\to$ curr[1] (3) $\ge$ intervals[1][0] (2) (True!)

• Merge: Stretch end boundary $\to$ curr[1] = Math.max(3, 6) = 6.

• curr state becomes [1, 6].

• i = 2 ([8, 10]): Check overlap $\to$ curr[1] (6) $\ge$ intervals[2][0] (8) (False! Gap found)

• Commit: ans.add([1, 6])

• Shift: curr = [8, 10]

• i = 3 ([15, 18]): Check overlap $\to$ curr[1] (10) $\ge$ intervals[3][0] (15) (False! Gap found)

• Commit: ans.add([8, 10])

• Shift: curr = [15, 18]

Step 3: Post-Loop Flush

The loop terminates, but the final active meeting group in curr ([15, 18]) has not been added yet.

• Flush: ans.add([15, 18])
• Final Result: [[1, 6], [8, 10], [15, 18]]

---

Key points

• Sorting First: Sorting by start time guarantees that all potential overlaps are strictly adjacent, turning complex graph operations into a simple 1D linear scan.
• Local State (curr) vs List Commit: Mutating curr[1] locally avoids updating reference pointers inside ans directly. ans.add() only triggers when a new disjoint interval is reached.
• Index Optimization (i = 1): Starting iteration at 1 avoids evaluating intervals[0] against itself, keeping the loop clean and eliminating redundant condition checks.
• The Post-Loop Flush: The last active interval group never encounters a subsequent “gap” to trigger ans.add(curr) inside the loop, making ans.add(curr) after loop completion necessary.
• Overflow Prevention: Always use Integer.compare(a[0], b[0]) instead of a[0] - b[0] to handle negative integer boundaries safely without arithmetic overflow.
• Loop starts fromi = 1 because we already initialized zero to current;