题目

给一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]] 

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。 

题解

这个题目关键两点：

1. 有序;
2. 可以合并;

我的思路很简单,你给的就是无重叠的,排好序的. 这时候我插入进去的时候： 1.要么有重叠(可能重叠多个),这时候我逐个合并即可; 2.要么没有重叠,大家相安无事; 我们模拟一下 case2 的过程：

[1,2],[3,5] (没有重叠) [1,2],[3,5],[4,8] -> [1,2],[3,8] (有重叠,合并.) [1,2],[3,8],[6,7] -> [1,2],[3,8] (有重叠,合并.) [1,2],[3,8],[8,10] -> [1,2],[3,10] (有重叠,合并.) [1,2],[3,10][12,16] (没有重叠) 

/** * 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; } * } */ class Solution { public List<Interval> insert(List<Interval> intervals, Interval newInterval) { intervals.add(newInterval); //按照 start 升序排列,原来的顺序也是能保证的. intervals.sort(Comparator.comparingInt(e -> e.start)); List<Interval> newList = new ArrayList<>(); newList.add(intervals.get(0)); for(int i=1; i< intervals.size() ; i++) { Interval entry = intervals.get(i); Interval last = newList.get(newList.size()-1); if (last.start <= entry.start && last.end >= entry.start) { //有重叠,合并. last.end = Math.max(entry.end,last.end); } else { //没有重叠 newList.add(entry); } } return newList; } } 

热门阅读

• [ Leetcode ] 56. 合并区间
• [ java ] CountDownLatch 运用场景（ 1 ）