牛客题解-NC37合并区间

发表于 更新于 分类于 阅读次数：

题目

给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

输入：

1
[[10,30],[20,60],[80,100],[150,180]]

返回值：

1
[[10,60],[80,100],[150,180]]

思路

分析

利用Collections.sort()方法对每一个区间的左区间进行排序，然后从第一个序列进行遍历，当后一个区间的右区间，小于或者等于后一个区间的左区间时，然后继续遍历下一个区间的左区间，并与下下个区间的右区间继续比较......直到后一个左区间大于后一个的右区间时，合并前面的多个区间，并寻找下一个合并区间，直到结束。

实现

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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        Collections.sort(intervals,(a,b)->a.start-b.start);
        int len = intervals.size();
        int i = 0;
        while (i < len) {
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;
            while (i < len-1 && intervals.get(i+1).start <= right) {
                right = Math.max(right,intervals.get(i+1).end);
                i++;
            }
            res.add(new Interval(left,right));
            i++;
        }
        return res;
    }
}