#56 Merge INtervals

56.Merge Intervals

Interval

Sorting

Problem Statement:

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:

Input:

[[1,3], [2,6], [8,10], [15,18]]

→

Output:

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

Since intervals [1,3] and [2,6] overlap, they are merged into [1,6]

Algorithm:

1. Sort intervals by start time
2. Initialize result array with first interval
3. For each interval, either merge with previous or add as new
4. Convert result list to array and return

public int[][] merge(int[][] intervals) {
    List<int[]> res = new ArrayList();

    // Sort intervals by start time for linear traversal
    Arrays.sort(intervals, (a,b) -> a[0] - b[0]);

    for (int[] interval: intervals) {
        // Get last interval from result array if exists
        int[] last = res.size() != 0 ? res.get(res.size() -1) : null;

        // Add new interval if no overlap
        if (res.size() == 0 || interval[0] > last[1]) 
            res.add(interval);
        else 
            last[1] = Math.max(last[1], interval[1]);
    }

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

Complexity:

Time: O(n log n) | Space: O(n)