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 public List<Interval> insert (List<Interval> intervals, Interval newInterval) intervals.add(newInterval); Collections.sort(intervals, new Comparator<Interval>() { 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; } }
近期评论