Medium

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.

Examples

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

Output:[[1,6],[8,10],[15,18]]

Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Input:intervals = [[1,4],[4,5]]

Output:[[1,5]]

Intervals [1,4] and [4,5] are considered overlapping.

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

Sort and Merge

Approach

First, we sort the intervals based on their start times. We initialize our result list and add the first interval to it. Then, we iterate through the remaining intervals. For each interval, we compare its start time with the end time of the last interval in our result list. If the current interval's start time is less than or equal to the last interval's end time, they overlap, so we merge them by updating the last interval's end time to `max(last.end, current.end)`. If they do not overlap, we simply add the current interval to the result list.

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

Time complexity is O(n log n) due to the sorting step. The iteration takes O(n). Space complexity is O(n) to store the result (and sorting might take O(n) space depending on the language implementation).

Solution.java

1class Solution {2    public int[][] merge(int[][] intervals) {3        if (intervals.length <= 1) {4            return intervals;5        }6        7        // Sort by starting time8        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));9        10        List<int[]> res = new ArrayList<>();11        int[] currentInterval = intervals[0];12        res.add(currentInterval);13        14        for (int[] interval : intervals) {15            int currentEnd = currentInterval[1];16            int nextBegin = interval[0];17            int nextEnd = interval[1];18            19            // Overlapping intervals20            if (currentEnd >= nextBegin) {21                currentInterval[1] = Math.max(currentEnd, nextEnd);22            } else {23                // Non-overlapping, add to result and update current24                currentInterval = interval;25                res.add(currentInterval);26            }27        }28        29        return res.toArray(new int[res.size()][]);30    }31}