Merge Intervals
Example
Given intervals => merged intervals:
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
思路
先按所有区间的起点排序，然后用pre和cur两个指针，如果有交集进行merge操作，否则pre向后移动。由于要求O(1)的space，就对原数组直接进行操作了。
时间复杂度O(nlogn)是Collections.sort()的时间。for循环是O(n)。
这道题有两个点：
学会使用Collections.sort(object, new Comparator<ObjectType>(){})进行排序;
对于要进行更改的数组而言，其一，for循环不要用for (a: A)的形式，会出现ConcurrentModificationException的编译错误，文档是这样解释的：it is not generally permissible for one thread to modify a Collection while another thread is iterating over it. 其二，对intervals的cur元素进行删除操作之后，对应的index i要减去1。
解法
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() <= 1) return intervals;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});
Interval pre = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval cur = intervals.get(i);
if (pre.end >= cur.start) {
pre.end = Math.max(pre.end, cur.end);
intervals.remove(cur);
i--;
}
else {
pre = cur;
}
}
return intervals;
}
}
Insert Intervals
Example
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5]
[1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9]
[1,2],[3,10],[12,16].
思路
和Merge Interval的思路接近，这题中我们只有一个待合并的Interval，就是输入给出的。我们只要把所有和该Interval有重叠的合并到一起就行了。为了方便操作，对于那些没有重叠部分的Interval，我们可以把在待合并Interval之前的Interval加入一个列表中，把之后的Interval加入另一个列表中。最后把前半部分的列表，合并后的大Interval和后半部分的列表连起来，就是结果了。
注意
因为待合并的Interval出现的位置不确定，判断重叠与否时既要判断起点，也要判断终点
原列表为空时，直接加入待合并的Interval后返回
解法
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> before = new LinkedList<Interval>();
List<Interval> after = new LinkedList<Interval>();
List<Interval> res = new LinkedList<Interval>();
if(intervals.size() == 0){
res.add(newInterval);
return res;
}
// 排序
Collections.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2){
return i1.start - i2.start;
}
});
for(Interval itx : intervals){
// 将待合并Interval之前的存入一个列表中
if(newInterval.start > itx.end){
before.add(itx);
}
// 将有重叠的Interval都合并起来
if((newInterval.end >= itx.start && newInterval.end <= itx.end) || (newInterval.start <= itx.end && newInterval.start >= itx.start)){
newInterval.start = Math.min(newInterval.start, itx.start);
newInterval.end = Math.max(newInterval.end, itx.end);
}
// 将待合并Interval之后的存入一个列表中
if(newInterval.end < itx.start){
after.add(itx);
}
}
// 把三部分加起来
res.addAll(before);
res.add(newInterval);
res.addAll(after);
return res;
}
}
