Back to DSA

Merge Intervals

hard
Acceptance: 41%
IntervalsSortingArrays

Given a list of intervals [start, end], combine every pair of intervals that overlaps into a single interval. Return the resulting list of merged intervals sorted by start value.

Examples

Example 1:
Input:intervals = [[2,4],[1,3],[7,9],[8,11]]
Output:[[1,4],[7,11]]
Example 2:
Input:intervals = [[1,5],[5,8]]
Output:[[1,8]]

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyBest Time to Buy and Sell StockeasyTwo SumeasyMerge Sorted ArrayeasyMove Zeroeseasy
00:00
import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            if (intervals[i][0] <= last[1]) {
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                merged.add(intervals[i]);
            }
        }
        return merged.toArray(new int[0][]);
    }
}
Time complexityO(n log n)
Space complexityO(n)