/ Data Structure and Algorithms  

Leetcode 56. Merge Intervals

Question



Merge the intervals that have overlaps.

Similar Questions

Solution

Suppose given an array of size n, then we assume that the first n-1 elements has been merged. What we have to solve now is the remaining one, how to add it to the n-1 elements that have been merged.

What we can do here is first sort the whole array by the left endpoint of the interval. Then loop the whole array, and adding in the new one with the last element of already merged intervals.



After sorting, we can simply compare the new interval with the last interval in the result set, see if they have overlap.

  • Case 1: If the left endpoint of the new interval is greater than the right endpoint of the last interval of the result list, then just add the new interval directly.

For example:
Result list: (1, 6), (8, 12)
New interval:                   (15, 19)
New result list: (1, 6), (8, 12), (15, 19)

  • Case 2: If the left endpoint of the new interval is not larger than the right endpoint of the last interval of the result list then only the right endpoint of the new interval and the right endpoint of last interval of the result list need to be determined.

Result list: (1, 6), (8, 12), (15, 19)
New interval:                      (17, 21)
New result list: (1, 6), (8, 12), (15, 21)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][0];
    }

    // result list
    List<List<Integer>> listResults = new ArrayList<>();

    // sort the input, use the left endpoint as key to sort
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

    // add the first element
    listResults.add(Arrays.stream(intervals[0]).boxed().collect(Collectors.toList()));
    

    for (int i = 1; i < intervals.length; i++) {
        // get last element in the result list
        Integer[] previous = listResults.get(listResults.size() - 1).toArray(new Integer[0]);

        // check if overlap
        if (isOverlap(previous, intervals[i])) {
            // if overlap, update the last element of result list
            listResults.get(listResults.size() - 1).set(0, Math.min(previous[0], intervals[i][0]));
            listResults.get(listResults.size() - 1).set(1, Math.max(previous[1], intervals[i][1]));
        } else {
            // add new interval to the result set
            listResults.add(Arrays.stream(intervals[i]).boxed().collect(Collectors.toList()));
        }
    }

    // convert to 2d array
    int[][] results = new int[listResults.size()][2];
    for (int i = 0; i < listResults.size(); i++) {
        results[i][0] = listResults.get(i).get(0);
        results[i][1] = listResults.get(i).get(1);
    }

    return results;
}

// determine if 2 intervals overlap
private boolean isOverlap(Integer[] a, int[] b) {
    return !(a[1] < b[0]);
}