Obsidian Notes

2. Merge Intervals

2 min read

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()][]);
    }
}

Backlinks