Approach

Merge Intervals

Problem Statement

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.

Examples

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 <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

Approach

Key Insight

Sort first, then merge!

After sorting by start time:

If current interval overlaps with previous → merge
Otherwise → add previous and start new interval

Two intervals overlap if: start2 <= end1

Solution 1: Sort and Merge

Sort by start time, then merge overlapping intervals.

Algorithm:

Sort intervals by start time
Initialize result with first interval
For each interval:
- If overlaps with last in result → merge (extend end)
- Otherwise → add to result
Return result

Solution 2: In-Place Modification

Modify input array directly.

Algorithm:

Sort intervals
Use write pointer to track result position
Merge overlapping intervals in-place
Return result[:write_index]

Solution 3: Stack-Based

Use stack to track merged intervals.

Algorithm:

Sort intervals
Push first interval to stack
For each interval:
- If overlaps with top → merge and update top
- Otherwise → push to stack
Return stack contents

Complexity Analysis

All Solutions:

Time Complexity: O(n log n) - dominated by sorting
Space Complexity: O(n) - for result array (or O(log n) if using in-place sort)

Pattern Recognition

This problem demonstrates:

Interval merging pattern
Sorting as preprocessing
Greedy approach after sorting
Foundation for meeting rooms, calendar problems
Used in scheduling, timeline problems

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: Sort and Merge
5    public int[][] merge(int[][] intervals) {
6        if (intervals.length == 0) return new int[0][];
7
8        // Sort by start time
9        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
10
11        List<int[]> merged = new ArrayList<>();
12        merged.add(intervals[0]);
13
14        for (int i = 1; i < intervals.length; i++) {
15            int[] current = intervals[i];
16            int[] last = merged.get(merged.size() - 1);
17
18            // If overlaps, merge
19            if (current[0] <= last[1]) {
20                last[1] = Math.max(last[1], current[1]);
21            } else {
22                // No overlap, add new interval
23                merged.add(current);
24            }
25        }
26
27        return merged.toArray(new int[merged.size()][]);
28    }
29
30    // Solution 2: Cleaner Version
31    public int[][] mergeClean(int[][] intervals) {
32        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
33        LinkedList<int[]> result = new LinkedList<>();
34
35        for (int[] interval : intervals) {
36            // If result is empty or no overlap
37            if (result.isEmpty() || result.getLast()[1] < interval[0]) {
38                result.add(interval);
39            } else {
40                // Merge: extend end of last interval
41                result.getLast()[1] = Math.max(result.getLast()[1], interval[1]);
42            }
43        }
44
45        return result.toArray(new int[result.size()][]);
46    }
47
48    // Solution 3: Using Stack
49    public int[][] mergeStack(int[][] intervals) {
50        if (intervals.length == 0) return new int[0][];
51
52        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
53        Stack<int[]> stack = new Stack<>();
54        stack.push(intervals[0]);
55
56        for (int i = 1; i < intervals.length; i++) {
57            int[] top = stack.peek();
58            int[] current = intervals[i];
59
60            if (current[0] <= top[1]) {
61                // Merge
62                top[1] = Math.max(top[1], current[1]);
63            } else {
64                // No overlap
65                stack.push(current);
66            }
67        }
68
69        return stack.toArray(new int[stack.size()][]);
70    }
71}
72