56. Merge Intervals

Problem

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. (link)

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<sup>4</sup>

• intervals[i].length == 2

• 0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>4</sup>

Solution

The main idea is to sort the whole array. This enables pairs, such that overlapping pairs will fall near to the same neighbor. The overlapping condition for any two pairs (a, b) and (c, d) is b <= c.

We combine the intervals by using two variables, start and end. We initially point the start and end to the first interval. We go on expanding the end until we see there is no overlap with the interval. If there is no overlap, then we add the interval (start, end) to the answer and start fresh by pointing (start, end) to the current interval. Finally, we add the interval (start, end) to the answer as it has the last interval range.

Time - O(nlogn)

Space - O(n)

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

        List<List<Integer>> ans = new ArrayList<>();

        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int[] interval: intervals){
            if(end>=interval[0]){
                end = Math.max(end, interval[1]);
            }
            else{
                ans.add(Arrays.asList(start,end));
                start = interval[0];
                end = interval[1];
            }
        }

        ans.add(Arrays.asList(start,end));

        int[][] res = ans.stream().map(l->l.stream().mapToInt(Integer::intValue).toArray()).toArray(int[][]::new);

        return res;
    }
}