給出一個區(qū)間的集合梗劫，請合并所有重疊的區(qū)間丛楚。
示例 1:
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2:
輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間届慈。
解題思路：
* 根據(jù)對象的start 升序排序
* 遍歷對象列表
* 如果當前結果列表最后一個元素end比下一個元素的start小 則把下一個加入到結果列表
* 否則 將當前結果列表中最后一個元素的end賦值 = max(res.get(last()).end, current.end)
java
public class Solution {
public class Interval {
int start;
int end;
Interval() { start = 0; end = 0; }
Interval(int s, int e) { start = s; end = e; }
}
/**
* 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; }
* }
*/
public List<Interval> merge(List<Interval> intervals) {
// 根據(jù)start排序
Collections.sort(intervals, (x,y) -> (x.start - y.start));
LinkedList<Interval> res = new LinkedList<>();
for (Interval inerval: intervals
) {
if (res.isEmpty() || res.peekLast().end < inerval.start) {
res.addLast(inerval);
} else {
res.peekLast().end = Math.max(inerval.end, res.peekLast().end );
}
}
return res;
}
}
python
# Definition for an interval.
class Interval:
def __init__(self, s=0, e=0):
self.start = s
self.end = e
class Solution:
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
intervals.sort(key=lambda x : x.start)
res = []
for interval in intervals:
if len(res) <= 0 or res[len(res)-1].end < interval.start:
res.append(interval)
else:
res[len(res)-1].end = max(res[len(res)-1].end, interval.end)
return res
