题目
给出若干闭合区间,合并所有重叠的部分。
http://www.lintcode.com/zh-cn/problem/merge-intervals/
分析
这题目看着很眼熟,之前有一道很类似的题目——插入区间(http://www.lintcode.com/zh-cn/problem/insert-interval/ )。显然只要把插入区间的代码借用过来,这道题目就搞定了,关于插入区间,解析可以参考https://www.hoyt-tian.com/cha-ru-qu-jian/
代码
class Item{
Interval interval;
int type = -1;
Item(Interval it, int type){
this.interval = it;
this.type = type;
}
}
public class Solution {
int type(Interval current, Interval target){
if(current.start > target.end){
return -1; //
}else if(target.end>=current.start && target.end<=current.end && current.start>target.start){
return 1; // left extend
}else if(target.start < current.start && target.end > current.end){
return 3; // contain
}else if(target.start>= current.start && target.end <= current.end){
return 0; // included
}else if(target.start>=current.start && target.start<= current.end){
return 2; // right extend;
}else if(target.start > current.end){
return -2; //
}
return -100;
}
/*
* @param intervals: Sorted interval list.
* @param newInterval: new interval.
* @return: A new interval list.
*/
public ArrayList insert(ArrayList intervals, Interval newInterval) {
// write your code here
if(intervals == null){
intervals = new ArrayList();
}
if(intervals.size() == 0){
intervals.add(newInterval);
return intervals;
}else if(intervals.size() == 1){
Interval current = intervals.get(0);
if(current.start > newInterval.end){
intervals.add(0, newInterval);
}
else if(current.end < newInterval.start){
intervals.add(newInterval);
}
else{
current.start = newInterval.startcurrent.end?newInterval.end:current.end;
}
return intervals;
}
Interval temp;
List- result = new ArrayList
- ();
for(int i=0; i
-1){
result.add(new Item(temp, type));
}
}
if(result.size() == 0){
Interval current, next;
for(int i=0; icurrent.end && newInterval.end < next.start){
intervals.add(i+1, newInterval);
return intervals;
}
}
intervals.add(newInterval);
return intervals;
}else{
Interval first = result.get(0).interval;
if(newInterval.start < first.start){
first.start = newInterval.start;
}
if(newInterval.end > first.end){
first.end = newInterval.end;
}
for(int i=1; i merge(List intervals) {
// write your code here
ArrayList result = new ArrayList<>();
if(intervals == null || intervals.size() < 1) return result;
result.add(intervals.get(0));
for(int i=1; i < intervals.size(); i++){
result = insert(result, intervals.get(i));
}
return (List)result;
}
}