Lintcode：合并区间

问题：

给出若干闭合区间，合并所有重叠的部分。

样例：

样例1:

输入: [(1,3)] 输出: [(1,3)]

样例 2:

输入: [(1,3),(2,6),(8,10),(15,18)] 输出: [(1,6),(8,10),(15,18)]

python：

""" Definition of Interval. class Interval(object): def __init__(self, start, end): self.start = start self.end = end """ class Solution: """ @param intervals: interval list. @return: A new interval list. """ def merge(self, intervals): # write your code here if len(intervals) <= 1: return intervals intervals = sorted(intervals, key=lambda x:x.start) result = [intervals[0]] for i in range(len(intervals)): if result[-1].end < intervals[i].start: result.append(intervals[i]) else: result[-1].end = max(result[-1].end, intervals[i].end) return result

C++：

/** * Definition of Interval: * classs Interval { * int start, end; * Interval(int start, int end) { * this->start = start; * this->end = end; * } * } */ class Solution { public: /** * @param intervals: interval list. * @return: A new interval list. */ vector<Interval> merge(vector<Interval> &intervals) { // write your code here if(intervals.size() <= 1) { return intervals; } sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b){return a.start < b.start;}); vector<Interval> result; result.push_back(intervals[0]); for(int i = 0; i < intervals.size(); i++) { if(result.back().end >= intervals[i].start) { result.back().end = max(result.back().end, intervals[i].end); }else{ result.push_back(intervals[i]); } } return result; } };