[LeetCode] 56. Merge Intervals

Posted on | Edited on | In |

Question

Given a collection of intervals, merge all overlapping intervals.

Example 1:

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:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

Soultion

這題的主要在考如何判斷兩個interval為重疊的演算法。

怎麼判斷兩個interval為重疊：

1.

1
2
i ：     |--------|
i'：  |-----|

2.

1
2
i ：     |--------|
i'：      |-----|

3.

1
2
i ：     |--------|
i'：           |-----|

4.

1
2
i ：     |--------|
i'：  |--------------|

以上為兩個interval重疊的情況，可以歸納出以下情況：

  • i.start <= i'.end
  • i'.start <= i.end

知道上述規則後合併就變得很簡單，因為給定的陣列是沒有排序過的，先依照 interval.start 排序。

  1. 初始化 merge = interval.get(0)
  2. 依序檢查 interval.get(i) 是否和 merge 重疊
  3. 若重疊，merge = 合併 interval.get(i) 和 merge
  4. 若不重疊，把 merge 寫入到結果，merge = interval.get(i)

有點像貪食蛇，就一直吃直到不能吃為止。

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
public List<Interval> merge(List<Interval> intervals) {
    List<Interval> result = new ArrayList<>();

    if (intervals.size() == 0 || intervals.size() == 1)
        return intervals;

    intervals.sort(Comparator.comparingInt(o -> o.start));

    Interval merge = intervals.get(0);
    for (int i = 1; i < intervals.size(); i++) {
        if (isOverlap(merge, intervals.get(i))) {
            merge = new Interval(
                    Math.min(merge.start, intervals.get(i).start),
                    Math.max(merge.end, intervals.get(i).end));
        } else {
            result.add(merge);
            merge = intervals.get(i);
        }
    }
    result.add(merge);

    return result;
}

private boolean isOverlap(Interval interval1, Interval interval2) {
    return interval1.start <= interval2.end && interval2.start <= interval1.end;
}