Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input:
[[1,3],[2,6],[8,10],[15,18]]
Output:
[[1,6],[8,10],[15,18]]
Explanation:
Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input:
[[1,4],[4,5]]
Output:
[[1,5]]
Explanation:
Intervals [1,4] and [4,5] are considerred overlapping.
思路是，先按interval的左端（start）排序。然后一个个检查是否能合并。下面这个做 in place 的替换。extra space O（1）
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
if not intervals:
return []
intervals.sort(key=lambda data: data.start)
storeIdx = 0
lo, hi = intervals[0].start, intervals[0].end
for i in xrange(1, len(intervals)):
if intervals[i].start > hi:
intervals[storeIdx] = Interval(lo, hi)
storeIdx += 1
lo, hi = intervals[i].start, intervals[i].end
else:
hi = max(hi, intervals[i].end)
intervals[storeIdx] = Interval(lo, hi) # 这行不能漏。从for循环出来的时候，还有一个interval在 lo，hi里。没加上
return intervals[: storeIdx + 1]
九章的一个solution
class Solution {
/**
* @param intervals, a collection of intervals
* @return: A new sorted interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
// write your code here
List<Interval> ans = new ArrayList<>();
intervals.sort(Comparator.comparing(i -> i.start)); //lambda 匿名函数：输入i 返回i.start
Interval last = null;
for (Interval item : intervals) {
if (last == null || last.end < item.start) {
ans.add(item);
last = item;
} else {
last.end = Math.max(last.end, item.end); // Modify the element already in list
}
}
return ans;
}
}