/**
* 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> merge(List<Interval> intervals) {
List<Integer> list = new ArrayList<>();
List<Interval> result = new ArrayList<>();
if(intervals.size() == 0){
return result;
}
HashMap<Integer, Interval> map = new HashMap<>();
for(int i = 0; i < intervals.size(); i++){
Interval interval = intervals.get(i);
if(!map.containsKey(interval.start)){
list.add(interval.start);
map.put(interval.start, interval);
} else {
Interval lastInterval = map.get(interval.start);
int end = Math.max(lastInterval.end, interval.end);
interval = new Interval(lastInterval.start, end);
map.put(interval.start, interval);
}
}
Collections.sort(list);
for(int i = 0 ; i < list.size()-1;i++){
Interval interval = map.get(list.get(i));
if(interval.end >= list.get(i+1)){
Interval next = map.get(list.get(i+1));
Interval mergedInterval = new Interval(interval.start, Math.max(interval.end, next.end));
map.put(list.get(i+1), mergedInterval);
} else {
result.add(interval);
}
}
result.add(map.get(list.get(list.size()-1)));
return result;
}
}
56.合并区间
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 题目： 总时间限制: 1000ms 内存限制: 65536kB描述给定 n 个闭区间 [ai; bi]，其中i=1...
