Algorithm-Day14-Merge-Intervals-lc-56

Posted on In , Views:

šŸ§© Problem Description

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

Example:

1
2
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

šŸ’” Brute Force? Not Ideal

You could check every pair and try to merge, but:

  • You would need to compare all combinations
  • āŒ Time complexity is too high (O(nĀ²) or worse)

šŸ’” Optimal Approach: Sort + Merge

āœØ Key Idea

  1. Sort the intervals by start time
  2. Iterate through intervals:
    • If the current interval overlaps with the previous one, merge them
    • Otherwise, add the previous interval to result

This approach ensures that we process all intervals in a linear scan after sorting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // Step 1: Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();

        int[] current = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            int[] next = intervals[i];

            if (current[1] >= next[0]) {
                // Merge overlapping intervals
                current[1] = Math.max(current[1], next[1]);
            } else {
                result.add(current);
                current = next;
            }
        }

        result.add(current); // Add the last interval

        return result.toArray(new int[result.size()][]);
    }
}

ā± Time and Space Complexity

  • Time Complexity: O(n log n)
    For sorting the intervals
  • Space Complexity: O(n)
    For the result list (output), auxiliary space is constant

āœļø Summary

  • This is a classic sort-then-scan problem
  • Make sure to handle edge cases like fully nested intervals (e.g., [1,10], [2,5])
  • Very common pattern in scheduling, calendar, and timeline problems

Sorting followed by greedy merging is a powerful approach for interval problems.