Leetcode(56) Merge Intervals

发表于 | 分类于

Description

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 considerred overlapping.

解法

这道题我最开始的思路是将输入中的区间依次加入结果list中，然后每次加入时与当前结果中所有的list相比较，结果发现比较的情况过于复杂，这个时候，如果将区间按照start排序然后再进行类似的处理，可以简化问题的处理方式。这告诉我们队一些复杂的数据进行排序可以简化处理流程。于是具体方法为，现将区间按start排序，每次先将区间加入结果list，再一一比较结果list中的相邻元素，做合并与删除操作。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return Integer.compare(o1.start, o2.start);
            }
        });
        List<Interval> res = new ArrayList<>();
        for (int i = 0; i < intervals.size(); i++) {
            res.add(intervals.get(i));
            for (int j = 0; j < res.size() - 1; j++) {
                Interval p = res.get(j);
                Interval q = res.get(j + 1);
                if (q.start <= p.end) {
                    p.end = Math.max(q.end, p.end);
                    res.remove(q);
                }
            }
        }
        return res;
    }
}