Leetcode(57) Insert Interval

发表于 | 分类于

Description

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

1
2
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

1
2
3
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

解法

此题解法与merge intervals 那题的解法类似，先不管是否重合可连接，将插入的区间直接扔到list中，对整个list排序，然后按照merge的方法进行合并即可。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        intervals.add(newInterval);
        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(p.end, q.end);
                    res.remove(q);
                }
            }
        }
        return res;
    }
}