[LeetCode] 56. Merge Intervals

Posted on | In

Problem

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Explanation 1

  1. We can change the input intervals to the following intervals: first start match the first end as one new interval, second start match the second end as one new interval, third start match the third interval as one new interval, etc. After changing, these intervals will have the same characteristic as the input intervals. For example, merging interval will have the same starting point and ending pointing, and their overlapping interval will be the same too.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     original interval:
 (1st)- - - - - - - - - - - - - - - - - -(3en)
           (3st)- - - - - - - - - -(2en)
       (2st)- - - - - - - -(1en)
                   (4st)- - - - - - - - - - - - -(4en)

 new created sort intervals:
 (1st)- - - - - - - - - - - -(1en)
       (2st)- - - - - - - - - - — -(2en)
           (3st)- - - - - - - - — - - -(3en)
                   (4st)- - - - - — - - - - — - -(4en)

 Before sort, all interval’s merge interval will be the same as the new created sorted merge interval.

  2. We can create a start array to hold all sorted starting points, and one end array to holds all sorted ending points. For example, start[] = {1, 4, 6, 8}, end[] = {2, 7, 9, 10}, then we create four intervals: {1, 2}, {4, 7}, {6, 9}, {8, 10} like the following:

    1
    2
    3
    4
    5
    6
     (1, 2)- - - -
            (4, 7)- - - - - - - -
                    (6, 9)- - - - - - - -
                            (8, 10)- - - - - -
 start:[1, 4, 6, 8]
 end:[2, 7, 9, 10]

  3. From the above example, we can see the first end 2 is less than the second start 4, so they are not overlapping. The second end 7 is greater than the third start 6, so they are overlapping; and the third end 9 is greater than the fourth start 8 so they are overlapping. So only the first interval is not overlapping. The other intervals are overlapping and merge to an interval starting with 4 and ending with 10.

Solution 1

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
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }

        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);

        int i = 0;
        while (i < intervals.length) {
            int st = start[i];
            while (i + 1 < intervals.length && end[i] >= start[i+1]) {
                i += 1;
            }
            int en = end[i];

            int[] temp = new int[2];
            temp[0] = st;
            temp[1] = en;
            res.add(temp);
            i += 1;
        }

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

Explanation 2

  1. First, sort the interval by their start time.

  2. To form an interval, we need a start and end. Initially, we initialize start is the first interval’s start time, end is the first interval’s end time.

  3. Loop from the second interval to the end, if the iterated interval’s start time is greater than end, we know they are disjoint. So we add an interval {start, end} to the result list. Then we update start be the iterated interval’s start time, end be the interval’s end time. In the next iteration, if the iterated interva’s start time is less than end, we only need to update end be the maximum of (end, intervals[i][1]), we don’t need to update start because we already sorted start from small to large, and we only need the minimum start and maximum end.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return new int[0][];
        Arrays.sort(intervals, (int[]a, int[] b) -> Integer.compare(a[0], b[0]));
        int start = intervals[0][0];
        int end = intervals[0][1];
        List<int[]> res = new ArrayList<>();
        for (int i = 1; i  < intervals.length; i++) {
            if (intervals[i][0] > end) {
                res.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            } else {
                end = Math.max(end, intervals[i][1]);
            }
        }
        res.add(new int[]{start, end});
        return res.toArray(new int[0][]);
    }
}